844. 比较含退格的字符串
力扣链接(简单)：https://leetcode.cn/problems/backspace-string-compare
给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。
注意：如果对空文本输入退格字符，文本继续为空。
示例 1：
| Text Only |
|---|
| 输入：s = "ab#c", t = "ad#c"
输出：true
解释：s 和 t 都会变成 "ac"。
|
示例 2：
| Text Only |
|---|
| 输入：s = "ab##", t = "c#d#"
输出：true
解释：s 和 t 都会变成 ""。
|
示例 3：
| Text Only |
|---|
| 输入：s = "a#c", t = "b"
输出：false
解释：s 会变成 "c"，但 t 仍然是 "b"。
|
提示：
1 <= s.length, t.length <= 200s 和 t 只含有小写字母以及字符 '#'
进阶：
- 你可以用
O(n) 的时间复杂度和 O(1) 的空间复杂度解决该问题吗？
个人题解
| C++ |
|---|
| class Solution {
public:
bool backspaceCompare(string s, string t) {
int leftIdx = 0, rightIdx = 0;
stack<char> a, b;
while(leftIdx < s.size() || rightIdx < t.size()){
//两个串分别用一个指针处理(双指针)
//非#入栈，遇#出栈即可
if(leftIdx < s.size()){
if (s[leftIdx] != '#') {
a.push(s[leftIdx]);
}
else if (!a.empty()){
a.pop();
}
leftIdx++;
}
if(rightIdx < t.size()){
if (t[rightIdx] != '#') {
b.push(t[rightIdx]);
}
else if (!b.empty()){
b.pop();
}
rightIdx++;
}
}
return a == b ? true : false;
}
};
|
官方题解
双指针
思路及算法
一个字符是否会被删掉，只取决于该字符后面的退格符，而与该字符前面的退格符无关。因此当我们逆序地遍历字符串，就可以立即确定当前字符是否会被删掉。
具体地，我们定义 skip 表示当前待删除的字符的数量。每次我们遍历到一个字符：
若该字符为退格符，则我们需要多删除一个普通字符，我们让 skip 加 1；
若该字符为普通字符：
若 skip 为 0，则说明当前字符不需要删去；
若 skip 不为 0，则说明当前字符需要删去，我们让 skip 减 1。
这样，我们定义两个指针，分别指向两字符串的末尾。每次我们让两指针逆序地遍历两字符串，直到两字符串能够各自确定一个字符，然后将这两个字符进行比较。重复这一过程直到找到的两个字符不相等，或遍历完字符串为止。
| 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;
}
};
|
复杂度分析