比较含退格的字符串001

本文主要是介绍比较含退格的字符串001，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1、描述

844给定 S 和 T 两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。 # 代表退格字符。

注意：如果对空文本输入退格字符，文本继续为空。

示例 1：

输入：S = “ab#c”, T = “ad#c”
输出：true
解释：S 和 T 都会变成 “ac”。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/backspace-string-compare
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2、关键字

退格，相等

3、思路

栈

4、notes

用两个栈一起使用

5、复杂度

时间：O(N+M）两个string的字符的个数
空间：O（N+M）

6、code

class Solution {
public:bool backspaceCompare(string S, string T) {if(S.size()==0||T.size()==0) return true;  // 特判bool flag=true;  // 答案stack<char>sta1;stack<char>sta2;int num1=0,num2=0;  //统计个数for(auto s:S)  // 遍历一个串，构造第一个栈   初始化两个栈{if(s!='#')  // 压栈{sta1.push(s);num1++;  // 栈个数加一}else {if(!sta1.empty())  // 遇到退格键，如果栈非空，就pop（）一个{sta1.pop();num1--;}else ; }}for(auto t:T){if(t!='#'){sta2.push(t);num2++;}else{if(!sta2.empty()){sta2.pop();num2--;}else;} }if(num1!=num2) return false;  //解答案：个数不等直接返回falsewhile(num1--)  // 个数相等{if(sta1.top()==sta2.top())  //栈顶相等{sta1.pop();sta2.pop();}else{flag=false;break;}            }return flag;}
};

这篇关于比较含退格的字符串001的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---