AlgoPressAppearance
0844-比较含退格的字符串
https://leetcode.cn/problems/backspace-string-compare
给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。
注意：如果对空文本输入退格字符，文本继续为空。
示例 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 = "b"
输出：false
解释：s 会变成 "c"，但 t 仍然是 "b"。
提示：
- 1 <= s.length, t.length <= 200
- s 和 t 只含有小写字母以及字符 '#'
进阶：
你可以用 O(n) 的时间复杂度和 O(1) 的空间复杂度解决该问题吗？
思路 ： 双指针
使用双指针，如果没有遇到#的时候，复制当前字符串，如果遇到则将前一个指针往前退1即 i-1，然后继续循环，这样j+1，就等于删掉了一个字符和 #
将两个字符串同样操作，最后比较结束位置后每个字符串的值是否相等。
参考代码
csharp
public class Solution {
public bool BackspaceCompare(string s, string t) {
int i0=0;
int j0=0;
char[] ss = s.ToCharArray();
while(j0 < ss.Length){
if(ss[j0] == '#'){
i0 -= 1;
i0 = Math.Max(i0,0);
}
else{
ss[i0] = ss[j0];
i0++;
}
j0++;
}
char[] tt = t.ToCharArray();
int i1 = 0;
int j1 = 0;
while(j1 < tt.Length){
if(tt[j1] == '#'){
i1 -= 1;
i1 = Math.Max(i1,0);
}
else{
tt[i1] = tt[j1];
i1++;
}
j1++;
}
//Console.WriteLine("i0={0},i1={1}",i0,i1);
if(i0 != i1){
return false;
}
for(int i = 0; i<i0; i++){
if(ss[i] != tt[i]){
return false;
}
}
return true;
}
}
思路2 ： 栈
根据定义，将两个字符串分别放入栈中，遇到正常字符就压栈，遇到退格#就出栈。
最后比较两个栈的元素是否相等
csharp
public class Solution {
public bool BackspaceCompare(string s, string t) {
Stack<char> stackS = new Stack<char>();
Stack<char> stackT = new Stack<char>();
for(int i=0; i<s.Length; i++){
if(s[i] != '#'){
stackS.Push(s[i]);
}
else{
if(stackS.Count > 0){
stackS.Pop();
}
}
}
for(int i=0; i<t.Length; i++){
if(t[i] != '#'){
stackT.Push(t[i]);
}
else{
if(stackT.Count > 0){
stackT.Pop();
}
}
}
if(stackT.Count != stackS.Count){
return false;
}
while(stackS.Count > 0){
if(stackS.Pop() != stackT.Pop()){
return false;
}
}
return true;
}
}
思路3 ： 双指针，从后往前计算
双指针，从后往前计算，遇到 # 则 skip + 1, 一直循环到 skip 结束，然后比较两个字符。 这个方法并不优雅，计算前置边界比较麻烦
csharp
public class Solution{
public bool BackspaceCompare(string s, string t){
int i = s.Length - 1;
int j = t.Length - 1;
while(i >= 0 || j >= 0){
int skipI = 0;
int skipJ = 0;
//寻找 i 的有效位置
while(i>=0){
if(s[i] == '#'){
skipI++;
i--;
}
else if(skipI > 0){
i--;
skipI--;
}
else{
break;
}
}
//Console.WriteLine("i={0}",i);
//寻找 j 的有效位置
while(j>=0){
if(t[j] == '#'){
skipJ++;
j--;
}
else if(skipJ > 0){
j--;
skipJ--;
}
else{
break;
}
}
//Console.WriteLine("j={0}",j);
if(i>=0 && j>=0 ){
if(s[i] != t[j]){
return false;
}
}
else if( i>=0 || j>=0){
return false;
}
i--;
j--;
}
return true;
}
}