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 <= S.length <= 200
1 <= T.length <= 200
S and T only contain lowercase letters and '#' characters.
Follow up: Can you solve it in O(N) time and O(1) space?
注意，这道题都是需要 time O(n) 和 space O(1)的，所以需要用 two pointer来做，注意最后结束条件：
class Solution {
public boolean backspaceCompare(String S, String T) {
if(S == null || T == null){
return false;
}
int i1 = S.length()-1;
int count1= 0;
int i2 = T.length()-1;
int count2 = 0;
while(i1 >= 0 || i2 >= 0){
if(i1 >= 0 && S.charAt(i1) == '#'){
count1++;
i1--;
}
else if (i2 >= 0 && T.charAt(i2) == '#'){
count2++;
i2--;
}
else if( i1 >= 0 && S.charAt(i1) != '#' && count1 > 0){
count1--;
i1--;
}
else if(i2 >= 0 && T.charAt(i2) != '#' && count2 > 0){
count2--;
i2--;
}
else{
if( i1>=0 && i2 >= 0 && S.charAt(i1) == T.charAt(i2) ){
i1--;
i2--;
}
else{
return false;
}
}
}
return true;
}
}