当前位置 博文首页 > jiiiiiaaaa的博客：【LeetCode】844. 比较含退格的字符串
给定 S 和 T 两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。 # 代表退格字符。
注意：如果对空文本输入退格字符，文本继续为空。
?
示例 1：
输入：S = "ab#c", T = "ad#c"
输出：true
解释：S 和 T 都会变成 “ac”。
示例 2：
输入：S = "ab##", T = "c#d#"
输出：true
解释：S 和 T 都会变成 “”。
示例 3：
输入：S = "a##c", T = "#a#c"
输出：true
解释：S 和 T 都会变成 “c”。
示例 4：
输入：S = "a#c", T = "b"
输出：false
解释：S 会变成 “c”，但 T 仍然是 “b”。
提示：
进阶：
你可以用 O(N) 的时间复杂度和 O(1) 的空间复杂度解决该问题吗？
?
思路及算法
最容易想到的方法是将给定的字符串中的退格符和应当被删除的字符都去除，还原给定字符串的一般形式。然后直接比较两字符串是否相等即可。
具体地，我们用栈处理遍历过程，每次我们遍历到一个字符：
C++
class Solution {
public:
bool backspaceCompare(string S, string T) {
return build(S) == build(T);
}
string build(string str) {
string ret;
for (char ch : str) {
if (ch != '#') {
ret.push_back(ch);
} else if (!ret.empty()) {
ret.pop_back();
}
}
return ret;
}
};
Python
class Solution:
def backspaceCompare(self, S: str, T: str) -> bool:
def build(s: str) -> str:
ret = list()
for ch in s:
if ch != "#":
ret.append(ch)
elif ret:
ret.pop()
return "".join(ret)
return build(S) == build(T)
复杂度分析
思路及算法
一个字符是否会被删掉，只取决于该字符后面的退格符，而与该字符前面的退格符无关。因此当我们逆序地遍历字符串，就可以立即确定当前字符是否会被删掉。
具体地，我们定义 skip 表示当前待删除的字符的数量。每次我们遍历到一个字符：
这样，我们定义两个指针，分别指向两字符串的末尾。每次我们让两指针逆序地遍历两字符串，直到两字符串能够各自确定一个字符，然后将这两个字符进行比较。重复这一过程直到找到的两个字符不相等，或遍历完字符串为止。
C++
class Solution {
public:
bool backspaceCompare(string S, string T) {
int i = S.length() - 1, j = T.length() - 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) {
if (S[i] != T[j]) {
return false;
}
} else {
if (i >= 0 || j >= 0) {
return false;
}
}
i--, j--;
}
return true;
}
};
Python
class Solution:
def backspaceCompare(self, S: str, T: str) -> bool:
i, j = len(S) - 1, len(T) - 1
skipS = skipT = 0
while i >= 0 or j >= 0:
while i >= 0:
if S[i] == "#":
skipS += 1
i -= 1
elif skipS > 0:
skipS -= 1
i -= 1
else:
break
while j >= 0:
if T[j] == "#":
skipT += 1
j -= 1
elif skipT > 0:
skipT -= 1
j -= 1
else:
break
if i >= 0 and j >= 0:
if S[i] != T[j]:
return False
elif i >= 0 or j >= 0:
return False
i -= 1
j -= 1
return True
复杂度分析
1、https://leetcode-cn.com/problems/backspace-string-compare/solution/bi-jiao-han-tui-ge-de-zi-fu-chuan-by-leetcode-solu/
cs