脚撕LeetCode(844)Easy
题目地址：https://leetcode-cn.com/problems/range-sum-query-mutable/
给定 S 和 T 两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。 # 代表退格字符。注意：如果对空文本输入退格字符，文本继续为空。 https://leetcode-cn.com/problems/backspace-string-compare
示例 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 只含有小写字母以及字符 '#'。 https://leetcode-cn.com/problems/backspace-string-compare
进阶： 你可以用 O(N) 的时间复杂度和 O(1) 的空间复杂度解决该问题吗？ 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/backspace-string-compare 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 https://leetcode-cn.com/problems/backspace-string-compare
要求：
时间复杂度O(N)，空间复杂度O(1)
思路：
一、暴力破解法
最直观的想到的就是暴力破解法，通过遍历两个数组，创造两个新数组，删除该删除的内容，然后对比。
时间复杂度O(N+M),空间复杂度O(N+M)；很明显这种做法不符合题意
执行结果：
110 / 110 个通过测试用例
状态：通过
执行用时: 1 ms
内存消耗: 36.6 MB
public static boolean backspaceCompareBP(String S, String T) {
return build(S).equals(build(T));
}
private static String build(String str) {
StringBuilder builder = new StringBuilder();
for (int i = 0; i < str.length(); i++) {
char ch = str.charAt(i);
if ('#' != ch) {
builder.append(ch);
} else {
if (builder.length() > 0) {
builder.deleteCharAt(builder.length() - 1);
}
}
}
return builder.toString();
}二、双指针计数法
这种方法需要在每个字符数组创建一个指针，并创建一个变量记录是否有需要删除的字符数量。因为#删除的是前一位的字符，所以我们倒叙遍历；
执行结果：
110 / 110 个通过测试用例
状态：通过
执行用时: 0 ms
内存消耗: 36.7 MB
public static boolean backspaceCompare(String S, String T) {
int skipS = 0, skipT = 0;
int sIndex = S.length() - 1, tIndex = T.length() - 1;
while (sIndex >= 0 || tIndex >= 0) {
while (sIndex >= 0) {
if (S.charAt(sIndex) == '#') {
skipS++;
sIndex--;
} else if (skipS > 0) {
skipS--;
sIndex--;
} else {
break;
}
}
while (tIndex >= 0) {
if (T.charAt(tIndex) == '#') {
skipT++;
tIndex--;
} else if (skipT > 0) {
skipT--;
tIndex--;
} else {
break;
}
}
if (sIndex >= 0 && tIndex >= 0) {
if (S.charAt(sIndex) != T.charAt(tIndex)) {
return false;
}
} else {
if (sIndex >= 0 || tIndex >= 0) {
return false;
}
}
sIndex--;
tIndex--;
}
return true;
}爆破法就不讲了，讲讲双指针法的思路：
首先，因为'#'字符串删除的是前面的字符，对于不构造一个新的空间装载数据的情况下，顺序遍历就显得鸡肋，所以我们采用倒叙遍历。
通过倒叙遍历(两者其中一者遍历完毕则循环终止)找到S字符串中没有被删除的字符与T字符串中没有被删除的字符对比，如果不相同则返回false；如果其中一个字符串遍历完成而另一个字符串没有遍历完成则返回false；当循环结束后，返回true；
那么，我们怎么实现找到没有被删除的字符串呢？
通过倒叙找到，如果此字符非'#'则返回，如果为'#'则变量skip++，再次循环这个字符串，直到skip = 0 且字符非'#'为止；
两个字符串都重复以上操作，找到需要对比的字符，进行对比。
以上就是leetcode.844.比较含退格符的字符串(easy)的全部内容
腾讯云开发者
