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
andT
only contain lowercase letters and'#'
characters.
Follow up:
- Can you solve it in
O(N)
time andO(1)
space?
class Solution {
public:
string process (string S) {
int i = 0, j = 0;
while (i < S.size()) {
if (S[i] == '#') {
if (j > 0) {
j--;
}
i++;
} else {
S[j++] = S[i++];
}
}
if (j == S.size()) {
return S;
}
return S.substr(0, j);
}
bool backspaceCompare(string S, string T) {
if (S == T) {
return true;
}
return process(S) == process(T);
}
};
No comments:
Post a Comment