844. Backspace String Compare

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?

-----------------
内部的while循环每次找到下一个非'#'的index

class Solution {
    public boolean backspaceCompare(String S, String T) {
        int m = S.length(), n = T.length();
        int i = m - 1, j = n - 1;
        int count1 = 0, count2 = 0;
        
        while (i >= 0 || j >= 0) {
            
            while (i >= 0) {
                if (S.charAt(i) == '#') {
                    count1++;
                    i--;
                }else if (count1 > 0) {
                    count1--;
                    i--;
                }else break;
            }
            
            while (j >= 0) {
                if (T.charAt(j) == '#') {
                    count2++;
                    j--;
                }else if (count2 > 0) {
                    count2--;
                    j--;
                }else break;
                
            }
            if (i >= 0 && j >= 0 && S.charAt(i) != T.charAt(j)) return false;
            if (i < 0 && j >= 0) return false;
            if (i >= 0 && j < 0) return false;
            i--;
            j--;
        }
        
        return true;
    }
}