# 844. Backspace String Compare

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. 1 <= S.length <= 200
2. 1 <= T.length <= 200
3. S and T only contain lowercase letters and '#' characters.

• Can you solve it in O(N) time and O(1)space?

class Solution {
public:
bool backspaceCompare(string S, string T) {
return helper(S) == helper(T);
}
string helper(string str) {
string res = "";
for (char c : str) {
if (c == '#') {
if (!res.empty()) res.pop_back();
} else {
res.push_back(c);
}
}
return res;
}
};

class Solution {
public:
bool backspaceCompare(string S, string T) {
string s = "", t = "";
for (char c : S) c == '#' ? s.size() > 0 ? s.pop_back() : void() : s.push_back(c);
for (char c : T) c == '#' ? t.size() > 0 ? t.pop_back() : void() : t.push_back(c);
return s == t;
}
};

class Solution {
public:
bool backspaceCompare(string S, string T) {
int i = (int)S.size() - 1, j = (int)T.size() - 1, cnt1 = 0, cnt2 = 0;
while (i >= 0 || j >= 0) {
while (i >= 0 && (S[i] == '#' || cnt1 > 0)) S[i--] == '#' ? ++cnt1 : --cnt1;
while (j >= 0 && (T[j] == '#' || cnt2 > 0)) T[j--] == '#' ? ++cnt2 : --cnt2;
if (i < 0 || j < 0) return i == j;
if (S[i--] != T[j--]) return false;
}
return i == j;
}
};

Github 同步地址：

https://github.com/grandyang/leetcode/issues/844

https://leetcode.com/problems/backspace-string-compare/

https://leetcode.com/problems/backspace-string-compare/discuss/135603/C%2B%2BJavaPython-O(N)-time-and-O(1)-space

https://leetcode.com/problems/backspace-string-compare/discuss/135873/8-lines-C%2B%2B-O(1)-space-easy-to-understand

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation