山西建设网站企业,手机网站跟pc网站有什么不同,孝义做网站的公司,wordpress 编辑图片844.比较含退格的字符串
题目描述
给定 s 和 t 两个字符串#xff0c;当它们分别被输入到空白的文本编辑器后#xff0c;如果两者相等#xff0c;返回 true 。# 代表退格字符。
注意#xff1a;如果对空文本输入退格字符#xff0c;文本继续为空。
示例 1#xff1a;…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 200s 和 t 只含有小写字母以及字符 ‘#’
进阶
你可以用 O(n) 的时间复杂度和 O(1) 的空间复杂度解决该问题吗
erase函数
// 定义一个解决方案类
class Solution {
public:// 定义一个公共成员函数来比较两个字符串 s 和 tbool backspaceCompare(string s, string t) {// 调用 my_erase 对字符串 s 进行处理my_erase(s);// 调用 my_erase 对字符串 t 进行处理my_erase(t);// 如果处理后的 s 和 t 相等返回 trueif(s t) return true;// 否则返回 falsereturn false;}private:// 定义一个私有成员函数 my_erase以引用方式接收字符串 str 并在原地修改void my_erase(string str){// 遍历字符串 strfor(int i 0; i str.size(); i){// 如果当前字符是退格符 #if(str[i] #)// 如果不位于字符串的开始位置if(i ! 0){// 删除前一个字符和当前的 # 字符str.erase(i - 1, 2);// 将索引 i 向后移动两个位置以重新检查新的当前位置的字符i - 2;}else{// 如果位于字符串的开始位置只删除 # 字符str.erase(i, 1);// 将索引 i 向后移动一个位置i - 1;}}}
};双指针
class Solution {
public:bool backspaceCompare(string s, string t) {// 初始化两个指针分别指向字符串 s 和 t 的末尾int is.size()-1,jt.size()-1;// 初始化两个变量用来记录需要退格的字符数int nums0, numt0;// 遍历两个字符串直到所有字符都被比较过while(i0||j0){// 在 s 中找到下一个应该比较的字符while(i0){//如果遇到退格符增加 s 中需要跳过的字符数并且指针向前移动if(s[i]#) nums, i--;// 如果有字符需要跳过减少需要跳过的字符数并且指针向前移动else if(nums0) nums--, i--;// 找到了应该比较的字符跳出循环else break;}// 在 t 中找到下一个应该比较的字符while(j0){if(t[j]#) numt,j--;else if(numt0) numt--,j--;else break;}// 比较 s 和 t 中的字符,如果字符不同返回 falseif(i0j0s[i]!t[j])return false;// 如果一个字符串结束而另一个没有结束也返回 falseif ((i 0) ! (j 0))//相当于if(i0j0||j0i0)return false;// 移动指针准备比较下一对字符i--,j--;}// 所有字符都匹配返回 truereturn true;}
};
