河南网站优化公司哪家好,wordpress 手机管理员密码,大理州建设局网站门户网,百度知道小程序每日一题(LeetCode)----数组–移除元素#xff08;四#xff09;
1.题目#xff08;[844. 比较含退格的字符串](https://leetcode.cn/problems/sqrtx/)#xff09;
给定 s 和 t 两个字符串#xff0c;当它们分别被输入到空白的文本编辑器后#xff0c;如果两者相等四
1.题目[844. 比较含退格的字符串](https://leetcode.cn/problems/sqrtx/)
给定 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 200s 和 t 只含有小写字母以及字符 #
进阶
你可以用 O(n) 的时间复杂度和 O(1) 的空间复杂度解决该问题吗
2.解题思路
思路一 重构字符串单指针
1.先将两个字符串中的退格字符和应该被删除的字符去除掉
我们用一个变量来存已经遍历到的退格字符的数量
然后我们从后向前遍历这两个字符串
如果遍历到的是退格字符那么删除退格字符然后记录已经遍历到退格字符的数量的变量进行加一操作
如果遍历到的是字符那我们看记录已经遍历到退格字符的数量的变量是否大于0
如果大于0删除当前遍历到的字符记录已经遍历到退格字符的数量的变量进行减一操作
如果小于0那么不进行操作进行向前遍历
2.然后将两个字符串进行比较
思路二 重构字符串栈
最容易想到的方法是将给定的字符串中的退格符和应当被删除的字符都去除还原给定字符串的一般形式。然后直接比较两字符串是否相等即可。
具体地我们用栈处理遍历过程每次我们遍历到一个字符
如果它是退格符那么我们将栈顶弹出
如果它是普通字符那么我们将其压入栈中。
原作者力扣官方题解
链接https://leetcode.cn/problems/backspace-string-compare/
3.写出代码
思路一的代码
class Solution {
public:bool backspaceCompare(string s, string t) {int length1 s.size();int length2 t.size();int sum1 0;int sum2 0;for (int i length1 - 1; i 0; i--) {if (s.size() 0) {break;}if (s[i] #) {s.erase(i, 1);sum1;}else {if (sum1 0) {s.erase(i, 1);sum1--;}}}for (int i length2 - 1; i 0; i--) {if (t.size() 0) {break;}if (t[i] #) {t.erase(i, 1);sum2;}else {if (sum2 0) {t.erase(i, 1);sum2--;}}}//进行比较if (s t) {return true;}else {return false;}}
};思路二的代码
class Solution {
public:bool backspaceCompare(string S, string T) {return build(S) build(T);}string build(string str) {string ret;for (char ch : str) {if (ch ! #) {ret.push_back(ch);} else if (!ret.empty()) {ret.pop_back();}}return ret;}
};原作者力扣官方题解
链接https://leetcode.cn/problems/backspace-string-compare/
