网站建设与策划试卷,山西响应式网页建设哪里好,铁路建设网站多少,甘肃网站建站系统平台给定 s 和 t 两个字符串#xff0c;当它们分别被输入到空白的文本编辑器后#xff0c;如果两者相等#xff0c;返回 true 。# 代表退格字符。
注意#xff1a;如果对空文本输入退格字符#xff0c;文本继续为空。
示例 1#xff1a;
输入#xff1a;s “ab#c”, t “a…给定 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) 的空间复杂度解决该问题吗
双指针两个指针开始时各自指向两个字符串尾部然后向前遍历即可
class Solution {
public:bool backspaceCompare(string s, string t) {int sIdx s.size() - 1;int tIdx t.size() - 1;int sDelete 0;int tDelete 0;while (sIdx 0 tIdx 0) {if (s[sIdx] #) {--sIdx;sDelete;continue;}if (t[tIdx] #) {--tIdx;tDelete;continue;}if (sDelete 0) {--sIdx;--sDelete;continue;}if (tDelete 0) {--tIdx;--tDelete;continue;}if (s[sIdx] ! t[tIdx]) {return false;}--sIdx;--tIdx;}// 以上循环结束时可能s或t其中一个还没有遍历完// s尚未遍历完由于t已被遍历完因此接下来s中不可以出现删不掉的字符while (sIdx 0) {if (s[sIdx] #) {--sIdx;sDelete;continue;}if (sDelete 0) {--sIdx;--sDelete;continue;}return false;}while (tIdx 0) {if (t[tIdx] #) {--tIdx;tDelete;continue;}if (tDelete 0) {--tIdx;--tDelete;continue;}return false;}return true;}
};如果s的长度为nt的长度为m则此算法时间复杂度为O(nm)空间复杂度为O(1)。
