给定 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”
方法一：重构字符串（栈的思想）
- 如果遇到退格符，则弹出栈顶元素
- 如果是普通字符，则入栈
java代码如下：
class Solution {
public boolean backspaceCompare(String s, String t){
StringBuilder sb1 = new StringBuilder();
StringBuilder sb2 = new StringBuilder();
for(char c : s.toCharArray()){
if(c != '#'){
sb1.append(c);
} else if (sb1.length() > 0){
sb1.deleteCharAt(sb1.length() - 1);
}
}
for(char c : t.toCharArray()){
if(c != '#'){
sb2.append(c);
} else if (sb2.length() > 0){
sb2.deleteCharAt(sb2.length() - 1);
}
}
return sb1.toString().equals(sb2.toString());
}
}
- 空间复杂度O（n）
方法二：双指针法
一个字符是否会被删掉，只取决于该字符后面的退格符，而与该字符前面的退格符无关
因此可以逆序地遍历字符串，就可以立即确定当前字符是否会被删掉
这里定义 skip表示当前要删除的字符的数量，每遍历到一个字符
- 如果字符是退格符，则
skip++，表示要删除一个字符 - 如果字符是普通字符：
（1）若skip == 0，则当前字符不需要删除
（2）若skip！= 0，则当前字符要删除，skip--
然后定义两个指针，分别指向两字符串的末尾；每次让两指针逆序地遍历两字符串，直到两字符串能够各自确定一个字符，然后将这两个字符进行比较；重复这一过程直到找到的两个字符不相等，或遍历完字符串为止。
java代码如下：
class Solution {
public boolean backspaceCompare(String s, String t){
int i = s.length() - 1;
int j = t.length() - 1 ;
int skipS = 0, skipT = 0;
while(i >= 0 || j >= 0){
while(i >= 0){
if(s.charAt(i) == '#'){
skipS++;
i--;
} else if (skipS > 0){
skipS--;
i--;
} else {
break;
}
}
while(j >= 0){
if(t.charAt(j) == '#'){
skipT++;
j--;
} else if (skipT > 0){
skipT--;
j--;
} else{
break;
}
}
if(i >= 0 && j >= 0){
if(s.charAt(i) != t.charAt(j)){
return false;
}
} else if(i >= 0 || j >= 0){
return false;
}
i--;
j--;
}
return true;
}
}
- 空间复杂度O（1）
Original: https://blog.csdn.net/qq_39473176/article/details/127808925
Author: HDU-五七小卡
Title: 代码随想录——比较含退格的字符串
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/656505/
转载文章受原作者版权保护。转载请注明原作者出处！