LeetCode 844. Backspace String Compare

原题链接在这里：https://leetcode.com/problems/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.

Input: S = "ab#c", T = "ad#c"
Output: true
Explanation: Both S and T become "ac".

Input: S = "ab##", T = "c#d#"
Output: true
Explanation: Both S and T become "".

Input: S = "a##c", T = "#a#c"
Output: true
Explanation: Both S and T become "c".

Input: S = "a#c", T = "b"
Output: false
Explanation: S becomes "c" while T becomes "b".

题解：

Could easily do it with stack. The follow up is to use O(N) time and O(1) space.

We could iterate the string back to front. Accumlate he # and use it when it is no #.

Then check if two chars are the same, if yes, move both pointers.

If not, check if two pointers alreay come to -1.

Time Complexity: O(m+n). m = S.length(). n = T.length().

Space: O(1).

AC Java:

class Solution {
    public boolean backspaceCompare(String S, String T) {
        if(S == null || T == null){
            return S == T;
        }
        
        int m = S.length();
        int n = T.length();
        int i = m - 1;
        int j = n - 1;
        int cntS = 0;
        int cntT = 0;
        
        while(i >= 0 || j >= 0){
            while(i >= 0 && (S.charAt(i) == ‘#‘ || cntS > 0)){
                if(S.charAt(i) == ‘#‘){
                    cntS++;
                }else{
                    cntS--;
                }
                
                i--;
            }
            
            while(j >= 0 && (T.charAt(j) == ‘#‘ || cntT > 0)){
                if(T.charAt(j) == ‘#‘){
                    cntT++;
                }else{
                    cntT--;
                }
                
                j--;
            }
            
            if(i >= 0 && j >= 0 && S.charAt(i) == T.charAt(j)){
                i--;
                j--;
            }else{
                return i == -1 && j == -1;
            }
        }
        
        return true;
    }
}