题目描述: 给定 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”。
提示：
1 <= S.length <= 200
1 <= T.length <= 200
S 和 T 只含有小写字母以及字符 ‘#’.
进阶：
你可以用 O(N) 的时间复杂度和 O(1) 的空间复杂度解决该问题吗？
来源： 力扣（LeetCode）
链接： https://leetcode-cn.com/problems/backspace-string-compare
解决方案:
思路一: 构造栈, 对于本题最直接的方法就是使用数据结构中的栈结构,构造一个栈, 当遇到退格字符 “#”, 就将退格字符”#“和它的下一个字符出栈。但是这样它的时间复杂度为O(N+M), 分别表示字符串S和T的长度, 空间复杂度也为O(N+M), 主要是申请栈空间所付出的内存开销。
思路二: 双指针法, 该方法可以弥补栈方法带来的时间和空间上多余的开销。由于退格字符”#”只对它的左边字符产生影响, 而不会给它的右边字符带来变化, 因此可以通过逆序遍历方式, 比较两个字符串中的字符是否匹配。
- 准备两个指针 i 和 j, 分别指向 字符串S，T 的末位字符，再准备两个变量 skipS 和 skipS，分别存放 S，T 字符串中的 # 数量。
- 从后往前遍历字符串，可能会遇到以下三种情况：
2.1 若当前字符是 #，则 skipS 自增 1；
2.2 若当前字符不是 #，且 skipS 不为 0，则 skipS 自减 1；
2.3 若当前字符不是 #，且 skipS为 0，则代表当前字符不会被消除，可以用来和字符串 T 中的当前字符作比较。
若对比过程出现 S, T 当前字符不匹配，则遍历结束，返回 false，若 S，T 都遍历结束，且都能一一匹配，则返回 true.
public static boolean backspaceCompare(String S, String T) {
int i = S.length() - 1, j = T.length() - 1;
// skipS 记录字符串S中退格字符的个数，skipT 记录字符串T中退格字符的个数
int skipS = 0, skipT = 0;
// 设置两个指针 i 和 j,从后往前遍历比较 S和 T中的字符
while (i >= 0 || j >= 0) {
// i >=0 表示字符串S遍历尚未结束
while (i >= 0) {
// 如果字符串S中的第i+1个字符为退格字符#
if (S.charAt(i) == '#') {
// 字符串S中的退格字符个数加1
skipS++;
// 字符串S中的指针向前移一个位置
i--;
} else if (skipS > 0) {
// 字符串S中的指针向前移一个位置
skipS--;
// 字符串S中的指针向前移一个位置
i--;
} else {
break;
}
}
// j>=0 表示字符串T遍历尚未结束
while (j >= 0) {
// 如果字符串T中的第j+1个字符为退格字符#
if (T.charAt(j) == '#') {
// 字符串T中的退格字符个数加1
skipT++;
// 字符串T中的指针向前移一个位置
j--;
} else if (skipT > 0) {
// 字符串T中的退格字符个数减1
skipT--;
// 字符串T中的指针向前移一个位置
j--;
} else {
break;
}
}
if (i >= 0 && j >= 0) {
// 字符串S中的第i+1个字符与字符串T中的第j+1个字符不匹配
if (S.charAt(i) != T.charAt(j)) {
// 判定为 false
return false;
}
} else {
// 字符串S或字符串T中只有一个遍历结束
if (i >= 0 || j >= 0) {
// 判定为 false
return false;
}
}
// 字符串S中的指针向前移一个位置
i--;
// 字符串T中的指针向前移一个位置
j--;
}
return true;
}
反思: 一开始是想到使用双指针法,从后往前遍历, 但是无奈格局太小, 一直盯着一个字符串看, 想着求出一个字符串最终的结果, 然后再调用同样的方法, 求出另一个字符串的最终结果, 最后对比两个结果, 看是否匹配。最后做下来, 根本没法通过所有的测试用例, 看了别人的题解才明白, 不得不佩服人家以及双指针思想的精妙之处, 继续努力吧!
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/5232.html
