-
Notifications
You must be signed in to change notification settings - Fork 22
Expand file tree
/
Copy path844.backspace-string-compare.cpp
More file actions
67 lines (63 loc) · 1.6 KB
/
844.backspace-string-compare.cpp
File metadata and controls
67 lines (63 loc) · 1.6 KB
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
// Tag: Two Pointers, String, Stack, Simulation
// Time: O(N)
// Space: O(1)
// Ref: -
// Note: -
// 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:
//
// 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 = "b"
// Output: false
// Explanation: s becomes "c" while t becomes "b".
//
//
// Constraints:
//
// 1 <= s.length, 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?
//
class Solution {
public:
bool backspaceCompare(string s, string t) {
int n = s.size();
int m = t.size();
int i = n - 1;
int j = m - 1;
int back = 0;
while (i >= 0 || j >= 0) {
back = 0;
while (i >= 0 && (s[i] == '#' || back > 0)) {
back += s[i] == '#' ? 1: -1;
i -= 1;
}
back = 0;
while (j >= 0 && (t[j] == '#' || back > 0)) {
back += t[j] == '#' ? 1 : -1;
j -= 1;
}
if (i == -1 || j == -1 || s[i] != t[j]) {
break;
}
i -= 1;
j -= 1;
}
return i == -1 && j == -1;
}
};