❓844. 比较含退格的字符串
难度:简单
给定 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(n) O(n) 的时间复杂度和 O ( 1 ) O(1) O(1) 的空间复杂度解决该问题吗?
💡思路:
法一:栈
- 使用栈将给定的字符串中的退格符
#
和 应当被删除的字符都去除; - 然后比较栈中两字符串是否相等即可。
法二:优化方法(从后向前双指针)
我们定义两个指针,分别指向两字符串的末尾( i
初始为 s
末尾,j
初始为 t
末尾),同时从后向前遍历 s
和 t
;
再定义 s_skip
和 t_skip
表示当前待删除的字符的数量。
每次我们遍历到一个字符:
- 该字符为退格符
#
,则我们需要多删除一个普通字符,我们让skip
加1
; - 若该字符为普通字符,让
skip
减1
;。
每次我们让两指针逆序地遍历两字符串,直到两字符串能够各自确定一个字符,然后将这两个字符进行比较。重复这一过程直到找到的两个字符不相等,或遍历完字符串为止。
动画如下:
🍁代码:(Java、C++)
法一:栈
Java
class Solution {
public boolean backspaceCompare(String s, String t) {
Stack<Character> stk1 = new Stack<>();
Stack<Character> stk2 = new Stack<>();
for(char c : s.toCharArray()){
if(c != '#') stk1.push(c);
else if(!stk1.empty()) stk1.pop();
}
for(char c : t.toCharArray()){
if(c != '#') stk2.push(c);
else if(!stk2.empty()) stk2.pop();
}
if(stk1.size() != stk2.size()) return false;
while(!stk1.empty()){
if(stk1.peek() != stk2.peek())return false;
stk1.pop();
stk2.pop();
}
return true;
}
}
C++
class Solution {
public:
bool backspaceCompare(string s, string t) {
stack<char> stk1, stk2;
for(char c : s){
if(c != '#') stk1.push(c);
else if(!stk1.empty()) stk1.pop();
}
for(char c : t){
if(c != '#') stk2.push(c);
else if(!stk2.empty()) stk2.pop();
}
if(stk1.size() != stk2.size()) return false;
while(!stk1.empty()){
if(stk1.top() != stk2.top())return false;
stk1.pop();
stk2.pop();
}
return true;
}
};
法二:优化方法(从后向前双指针)
Java
class Solution {
public boolean backspaceCompare(String s, String t) {
int i = s.length() - 1, j = t.length() - 1;
int s_skip = 0, t_skip = 0;
while(true){
while(i >= 0 && (s.charAt(i) == '#' || s_skip > 0)){// 从后向前,消除s的#
if(s.charAt(i) == '#') s_skip++;
else s_skip--;
i--;
}
while(j >= 0 && (t.charAt(j) == '#' || t_skip > 0)){// 从后向前,消除t的#
if(t.charAt(j) == '#') t_skip++;
else t_skip--;
j--;
}
// 后半部分#消除完了,接下来比较s[i] != t[j]
if (i < 0 || j < 0) break; // s 或者t 遍历到头了
if (s.charAt(i) != t.charAt(j)) return false;
i--;j--;
}
return i == j;
}
}
C++
class Solution {
public:
bool backspaceCompare(string s, string t) {
int i = s.size() - 1, j = t.size() - 1;
int s_skip = 0, t_skip = 0;
while(1){
while(i >= 0 && (s[i] == '#' || s_skip > 0)){// 从后向前,消除s的#
if(s[i] == '#') s_skip++;
else s_skip--;
i--;
}
while(j >= 0 && (t[j] == '#' || t_skip > 0)){// 从后向前,消除t的#
if(t[j] == '#') t_skip++;
else t_skip--;
j--;
}
// 后半部分#消除完了,接下来比较s[i] != t[j]
if (i < 0 || j < 0) break; // s 或者t 遍历到头了
if (s[i] != t[j]) return false;
i--;j--;
}
return i == j;
}
};
🚀 运行结果:
🕔 复杂度分析:
-
时间复杂度:
O
(
n
+
m
)
O(n+m)
O(n+m),其中
n
和m
分别为字符串s
和t
的长度。我们需要遍历两字符串各一次。 - 空间复杂度: O ( 1 ) O(1) O(1),对于每个字符串,我们只需要定义一个指针和一个计数器即可。法一为 O ( n + m ) O(n+m) O(n+m)。
题目来源:力扣。文章来源:https://www.toymoban.com/news/detail-514730.html
放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我LeetCode主页 / CSDN—力扣专栏,每日更新!文章来源地址https://www.toymoban.com/news/detail-514730.html
注: 如有不足,欢迎指正!
到了这里,关于(字符串) 844. 比较含退格的字符串——【Leetcode每日一题】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!