Gyh's Braindump

844. Backspace String Compare

tags
two pointers
source
leetcode

Edge Cases

"bbbextm"
"bbb#extm"

Solution

scan from end of strings

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) {  // see edge case
            while (i >= 0) {
                if (S.charAt(i) == '#') {
                    skipS++;
                    i--;
                } else if (skipS > 0) {
                    skipS--;
                    i--;
                } else {
                    break;
                }
            }
            while (j >= 0) {
                if (T.charAt(j) == '#') {
                    skipT++;
                    j--;
                } else if (skipT > 0) {
                    skipT--;
                    j--;
                } else {
                    break;
                }
            }

            if ((i >= 0) != (j >= 0)) return false;
            if (i >= 0 && j >= 0 && S.charAt(i) != T.charAt(j)) return false;
            i--;
            j--;
        }

        return true;
    }
}

Complexity

  • time: O(M+N)
  • space: O(1)