844. 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. 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?

My Solutions:

方法一：先处理两个string S和T，方法是用stringbuilder或者stack储存字母，碰到#就把最后一个字母删去。最后比较两个处理完的string。

Space: O(n)

public boolean backspaceCompare(String S, String T) {
    if (S.length() == 0 && T.length() == 0) return true;
    String s = convert(S);
    String t = convert(T);
    return s.equals(t);
}

public String convert(String str) {
    StringBuilder sb = new StringBuilder();
    for (char c : str.toCharArray()) {
        if (c == '#') {
            if (sb.length() == 0) continue; // 没有字母可以删，do nothing
            else sb.setLength(sb.length() - 1); // remove last char
        } else {
            sb.append(c);
        }
    }
    return sb.toString();
}

方法2：用两个pointer标记从string的末尾往前走，S和T会被保留的字母的index。然后比较这个index上S和T的字母是否相同，直到index<0。

Space: O(1)

public boolean backspaceCompare(String S, String T) {
    int s = S.length() - 1, t = T.length() - 1;
    while (s >= 0 || t >= 0) {
        s = moveBack(S, s);
        t = moveBack(T, t);
        if (s >= 0 && t >= 0 && S.charAt(s) != T.charAt(t)) return false;
        if (s < 0 || t < 0) return s == t;
        s--;
        t--;
    }
    return true;
}

public int moveBack(String str, int index) {
    int count = 0; // count how many chars need to be deleted
    while (index >= 0) {
        if (str.charAt(index) == '#') {
            count++;
            index--;
        } else if (count > 0) {
            count--;
            index--;
        } else {
            return index;
        }
    }
    return index;
}