LeetCode 844 比较含退格的字符串
LeetCode 844 比较含退格的字符串
LeetCode 844 比较含退格的字符串
力扣 844 比较含退格的字符串 | LeetCode 844 Backspace String Compare | 算尽天下系列第 11 期 | 栈/双指针
题目描述
给定 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(1) 的空间呢？这道题的难度一下子就可以上升好几个数量级。
下面分享一种使用双指针来完成这道题的方法，只需要使用 O(1) 的辅助空间。
从前往后遍历字符串的时候，遇到一个字符，我们是没有办法知道这个字符最终会不会属于这个字符串，因为我们没有办法知道后面会有多少个退格，但是从后往前遍历字符串的时候，我们有办法知道一个字符是不是属于这个字符串。
那么，我们可以从后往前遍历字符串，记 i 和 j 分别表示当前两个字符串的比较位置，初始均为 strlen() - 1。
若当前位置的字符不相等（S[i] != T[j]），则直接 return false 而无需继续往前比较，若当前位置的字符相等，那么继续往前比较。
现在还需要处理一个退格的问题。
若遇到 S[i] == '#'，那么就要数一数有多少个退格键，每遇到一个退格键，skipS++，表示接下来要跳过多少个字符。那么，当 skipS > 0 时，我们依旧需要持续地令 i--; skipS--;，不断的跳过那些被删除了的字符。
需要注意的有两点：一，在这个过程中，S[i] 依旧有可能等于 '#'，此时我们非但不应该进行 skipS--，反而应该进行 skipS++。二，在退格操作完成后，紧接着的那个字符也有可能是 '#'，因此退格操作应持续进行到 S[i] != '#' 为止。
对于 T 也是一样的。
只要 i 和 j 中有任何一个还大于 0，就应该持续该过程，直到两者都小于 0，此时输出 true。
由于字符串长度可能不等，退格键的按下次数可能会超过已经输入的字符数，例如 a###########b，所以应该时刻注意上面所有的条件判断中要加上 i >= 0 和 j >= 0 的判断。
这样，在上面过程中的任何一处出现 (i >= 0 && j < 0) 或者 (i < 0 && j >= 0) 都将是不合法的。
完整代码
bool backspaceCompare(char * S, char * T){
int i = strlen(S) - 1;
int j = strlen(T) - 1;
int skipS = 0;
int skipT = 0;
while (i >= 0 || j >= 0) {
while (i >= 0 && S[i] == '#') {
while (i >= 0 && S[i] == '#') {
skipS++;
i--;
}
while (i >= 0 && skipS > 0) {
if (S[i] == '#') {
skipS++;
} else {
skipS--;
}
i--;
}
}
while (j >= 0 && T[j] == '#') {
while (j >= 0 && T[j] == '#') {
skipT++;
j--;
}
while (j >= 0 && skipT > 0) {
if (T[j] == '#') {
skipT++;
} else {
skipT--;
}
j--;
}
}
if (i >=0 && j >= 0) {
if (S[i] != T[j]) {
return false;
} else {
i--;
j--;
}
} else {
return i < 0 && j < 0;
}
}
return true;
}官方的题解会更简洁一些：
class Solution {
public boolean 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 there may be chars in build(S) or build (T)
while (i >= 0) { // Find position of next possible char in build(S)
if (S.charAt(i) == '#') {skipS++; i--;}
else if (skipS > 0) {skipS--; i--;}
else break;
}
while (j >= 0) { // Find position of next possible char in build(T)
if (T.charAt(j) == '#') {skipT++; j--;}
else if (skipT > 0) {skipT--; j--;}
else break;
}
// If two actual characters are different
if (i >= 0 && j >= 0 && S.charAt(i) != T.charAt(j))
return false;
// If expecting to compare char vs nothing
if ((i >= 0) != (j >= 0))
return false;
i--; j--;
}
return true;
}
}参考资料
[1] https://www.jxtxzzw.com
腾讯云开发者
