Backspace String Compare

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

Example

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

最优解就是

• 记录#的数目，反向遍历。

• 当遇到#大于0的时候就跳过下一个字符，并减少#的count

• 如果遇到的是字符，且#的count是0，就相互直接比较

• i或者j应该同时到起点

比较不太好写

Code

class Solution {
    public boolean backspaceCompare(String S, String T) {
        if (S == null || T == null) {
            return true;
        }
        System.out.println(deal(S));
        System.out.println(deal(T));
        return deal(S).equals(deal(T));

    }

    private String deal(String S) {
        Stack<Character> stack = new Stack<>();
        //S = "a##c", T = "#a#c"
        for (char c : S.toCharArray()) {
            if (c == '#' && !stack.isEmpty()) {
                stack.pop();
            } else if (c != '#') {
                stack.push(c);
            }
        }
        return String.valueOf(stack);
    }
}

class Solution {
    public boolean backspaceCompare(String S, String T) {
        int i = S.length() - 1, j = T.length() - 1;
        int skipS = 0, skipT = 0;

        while (i >= 0 || j >= 0) { // While there may be chars in build(S) or build (T)
            while (i >= 0) { // Find position of next possible char in build(S)
                if (S.charAt(i) == '#') {skipS++; i--;}
                else if (skipS > 0) {skipS--; i--;}
                else break;
            }
            while (j >= 0) { // Find position of next possible char in build(T)
                if (T.charAt(j) == '#') {skipT++; j--;}
                else if (skipT > 0) {skipT--; j--;}
                else break;
            }
            // If two actual characters are different
            if (i >= 0 && j >= 0 && S.charAt(i) != T.charAt(j))
                return false;
            // If expecting to compare char vs nothing
            if ((i >= 0) != (j >= 0))
                return false;
            i--; j--;
        }
        return true;
    }
}