844. Backspace String Compare (easy)

Q:

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?

A:

就是从后往前比较，  同时用一个指针记录位置  （比较tricky,多练几遍）

class Solution {
public:
    bool backspaceCompare(string S, string T) {
        int is = S.length()-1;
        int it = T.length()-1;
        int cc = 0;
        while(is>=0 || it>=0)  // using && will omit case of S= "a#" T=""
        {
            cc = 0;
            while(is>=0 && ( S[is]=='#' || cc>0))
            {
                if(S[is] =='#')
                {
                    cc++;
                }else{
                    cc--;
                }            
                is--;
            }

            cc = 0;
            while(it>=0 && ( T[it]=='#' || cc>0))
            {
                if(T[it] =='#')
                {
                    cc++;
                }else{
                    cc--;
                }        
                it--;    
            }
            // now both are valid, do compare now.
            if(is<0 && it<0)
                return true;
            if(is<0 || it<0)
                return false;
            if(S[is] != T[it])
                return false;
            is--;
            it--;        
        }
        return is<0 && it<0; // not both index are out of range
    }
};