Backspace String Compare Problem
Description
LeetCode Problem 844.
Given two strings s and t, return true if they are equal when both are typed into empty text editors. ‘#’ means a backspace character.
Note that after backspacing an empty text, the text will continue empty.
Example 1:
1
2
3
Input: s = "ab#c", t = "ad#c"
Output: true
Explanation: Both s and t become "ac".
Example 2:
1
2
3
Input: s = "ab##", t = "c#d#"
Output: true
Explanation: Both s and t become "".
Example 3:
1
2
3
Input: s = "a##c", t = "#a#c"
Output: true
Explanation: Both s and t become "c".
Example 4:
1
2
3
Input: s = "a#c", t = "b"
Output: false
Explanation: s becomes "c" while t becomes "b".
Constraints:
- 1 <= s.length, t.length <= 200
- sand t only containlowercase letters and ‘#’ characters.
Sample C++ Code
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
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
bool backspaceCompare(string S, string T) {
int i = S.size() - 1;
int j = T.size() - 1;
int skipS = 0, skipT = 0;
while (i >= 0 || j >= 0) {
while (i >= 0) {
if (S[i] == '#') {
skipS ++; i --;
} else if (skipS > 0) {
skipS --; i --;
} else {
break;
}
}
while (j >= 0) {
if (T[j] == '#') {
skipT ++; j --;
} else if (skipT > 0) {
skipT --; j --;
} else {
break;
}
}
if (i >= 0 && j >= 0 && S[i] != T[j])
return false;
if ((i >= 0) != (j >= 0))
return false;
i --;
j --;
}
return true;
}
};