Formatted question description: https://leetcode.ca/all/844.html
844. Backspace String Compare (Easy)
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?
Solution 1.
Update the S
and T
to the results of applying backspaces, then compare the strings.
// OJ: https://leetcode.com/problems/backspace-string-compare/
// Time: O(N)
// Space: O(1)
class Solution {
string normalize(string &s) {
int len = 0;
for (char c : s) {
if (c == '#') len = max(len - 1, 0);
else s[len++] = c;
}
s.resize(len);
return s;
}
public:
bool backspaceCompare(string S, string T) {
return normalize(S) == normalize(T);
}
};
Solution 2.
If it’s not allowed to change the input string, we scan backward. back
function is used to skip all characters that are deleted using backspaces. After back
, the indexes are pointing to characters that we need to compare.
// OJ: https://leetcode.com/problems/backspace-string-compare/
// Time: O(N)
// Space: O(1)
class Solution {
void back(string &s, int &i) {
if (i < 0 || s[i] != '#') return;
int cnt = 0;
for (; i >= 0 && (cnt || s[i] == '#'); --i) {
if (s[i] == '#') ++cnt;
else --cnt;
}
}
public:
bool backspaceCompare(string S, string T) {
int i = S.size() - 1, j = T.size() - 1;
while (i >= 0 || j >= 0) {
back(S, i);
back(T, j);
if ((i >= 0 && j < 0) || (i < 0 && j >= 0)) return false;
for (; i >= 0 && j >= 0 && S[i] != '#' && T[j] != '#'; --i, --j) {
if (S[i] != T[j]) return false;
}
}
return true;
}
};
Java
-
class Solution { public boolean backspaceCompare(String S, String T) { StringBuffer sb1 = new StringBuffer(); StringBuffer sb2 = new StringBuffer(); int length1 = S.length(), length2 = T.length(); for (int i = 0; i < length1; i++) { char c = S.charAt(i); if (c == '#') { if (sb1.length() > 0) sb1.deleteCharAt(sb1.length() - 1); } else sb1.append(c); } for (int i = 0; i < length2; i++) { char c = T.charAt(i); if (c == '#') { if (sb2.length() > 0) sb2.deleteCharAt(sb2.length() - 1); } else sb2.append(c); } return sb1.toString().equals(sb2.toString()); } }
-
// OJ: https://leetcode.com/problems/backspace-string-compare/ // Time: O(N) // Space: O(1) class Solution { string normalize(string &s) { int len = 0; for (char c : s) { if (c == '#') len = max(len - 1, 0); else s[len++] = c; } s.resize(len); return s; } public: bool backspaceCompare(string S, string T) { return normalize(S) == normalize(T); } };
-
if s == '#': if ans_S: ans_S = ans_S[:-1]