30-Day LeetCoding Challenge - 9Day (Backspace String Compare)

Backspace String Compare

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 <= S.length <= 200
• 1 <= T.length <= 200
• S and T only contain lowercase letters and '#' characters.

Follow up:

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

S와 T에 문자열이 주어지는데 #은 Backspace key를 의미한다.
즉 S= "ab##"이면 ab후 Backspace 2번 이니 S=""가 남게되는 것 이다.
이럴 때 S와T가 같으면 true를 아니면 false를 반환하는 메소드를 작성하는 문제이다.

Solution

class Solution {
    public boolean backspaceCompare(String S, String T) {
    	Stack<Character> sStk = new Stack<>();
	Stack<Character> tStk = new Stack<>();

	for (int i = 0; i < S.length(); i++) {
		if (S.charAt(i) == '#') {
			if (sStk.size() > 0)
				sStk.pop();
		} else {
			sStk.push(S.charAt(i));
		}
	}
    
	for (int i = 0; i < T.length(); i++) {
		if (T.charAt(i) == '#') {
			if (tStk.size() > 0)
				tStk.pop();
		} else {
			tStk.push(T.charAt(i));
		}
	}

	if (sStk.equals(tStk))
		return true;
	else
		return false;
    }
}

• Stack을 이용해 Stack의 크기가 0보다 크고 (값이 있으면) String S의 i번째 문자가 '#'이 아니면 pop()을 아니면 push()를 하여 Stack sStk와 tStk의 값이 같은지 비교를 한다.
• 같으면 true 다르면 false를 반환!

마침

문제를 풀고 답지를 봤는데 같은 방식인데 훨씬 간단하게 풀 수 있었다.... 계속 문제를 풀면서 비슷한 for문인데 어떻게 하면 더 효율적으로 짤 수 있을까 고민했었는데 생각이 안나서 그냥 제출했는데 답지를 보니깐 나는 빡머가리인가보다 ㅜㅜ

Leetcode Solution

class Solution {
    public boolean backspaceCompare(String S, String T) {
        return build(S).equals(build(T));
    }

    public String build(String S) {
        Stack<Character> ans = new Stack();
        for (char c: S.toCharArray()) {
            if (c != '#')
                ans.push(c);
            else if (!ans.empty())
                ans.pop();
        }
        return String.valueOf(ans);
    }
}