Backspace String Compare

LeetCode 844번

Tags. Two Pointers, Stack

https://leetcode.com/problems/backspace-string-compare/

Backspace String Compare - LeetCode

 

문제

Given two strings S and T, return if they are equal when both are typed into empty text editors. # means a backspace character.

 

Example 1:

  Input: S = "ab#c", T = "ad#c"

  Output: true

Explanation: Both S and T become "ac".

 

Example 2:

  Input: S = "ab##", T = "c#d#"

  Output: true

Explanation: Both S and T become "".

 

Example 3:

  Input: S = "a##c", T = "#a#c"

  Output: true

Explanation: Both S and T become "c".

 

Example 4:

  Input: S = "a#c", T = "b"

  Output: false

Explanation: S becomes "c" while T becomes "b".

 

Note:

1. 1 <= S.length <= 200
2. 1 <= T.length <= 200
3. S and T only contain lowercase letters and '#' characters.

Follow up:

• Can you solve it in O(N) time and O(1) space?

Code

class Solution {
    
    Stack<Character> stack_S = new Stack<>();
    Stack<Character> stack_T = new Stack<>();
    
    public boolean backspaceCompare(String S, String T) {
        boolean result = true;
        
        char[] s = S.toCharArray();
        char[] t = T.toCharArray();
        
        for(int i = 0; i < s.length; i++) {
            if(s[i] == '#') {
                if(stack_S.size() != 0) {
                    stack_S.pop();
                }
            }else {
                stack_S.push(s[i]);
            }
        }
        for(int i = 0; i < t.length; i++) {
            if(t[i] == '#') {
                if(stack_T.size() != 0) {
                    stack_T.pop();
                }
            }else {
                stack_T.push(t[i]);
            }
        }
        
        if(stack_S.size() != stack_T.size()) {
            return false;
        }else {
            for(int i = 0; i < stack_S.size(); i++) {
                if(stack_S.pop() != stack_T.pop()) {
                    return false;
                }
            }
        }
        
        return result;
    }
}

 

Solution

두개의 문자열에 #이 존재하면 앞에 있는 문자를 삭제하고 결과적으로 두 문자열이 서로 같은지 판단하여 true, false값을 반환하는 문제이다.

 

문자열 두개이니 스택도 두개를 만들어서 각각 Char[] 에 넣고 각각 for문으로 문자가 들어오면 stack에 push(), '#'이 들어오면 pop() 을 하여 만든 두개의 스택의 size()와 순차적으로 pop()했을때 값을 비교하여 하나라도 다르면 그즉시 false를 반환하고 모두 같다면 true를 반환하게 만들었다.

 

Runtime : 2ms

Memory : 34.4MB