LeetCode [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?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

class Solution { void moveToLastValidChar(string S, int &index){ int cnt = 0;//number of '#' while(index>=0){ if(S[index] == '#'){ index--; cnt++; }else if(cnt>0){ index--; cnt--; }else{ break; } } } public: bool backspaceCompare(string S, string T) { int ns = S.size(), nt = T.size(), i = ns-1, j = nt-1; while(i>=0 || j>=0){ moveToLastValidChar(S, i); moveToLastValidChar(T, j); if(i>=0 && j>=0 && S[i]!=T[j]) return false; if((i<0 && j>=0)||(j<0 && i>=0)) return false; i--; j--; } return true; } };