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; } }