本文共 1730 字，大约阅读时间需要 5 分钟。

知识点：字符串

时间：2020年10月19日 题目链接：

题目

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

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

示例 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 = “#a#c” 输出：true 解释：S 和 T 都会变成 “c”。

示例 4：

输入：S = “a#c”, T = “b” 输出：false 解释：S 会变成 “c”，但 T 仍然是 “b”。

提示：

• 1 <= S.length <= 200
• 1 <= T.length <= 200
• S 和 T 只含有小写字母以及字符 ‘#’。

进阶：

你可以用 O(N) 的时间复杂度和 O(1) 的空间复杂度解决该问题吗？

解法

• 模拟 从头往后修改字符串 注意多个#的时候也就是string中没有字符了 就不用回退了
• 用指针从后往前模拟
  • 如果出现# 则下一个字符删去
  • 直到找到两个字符串的有效字符 比较
  • 不同 或者 两个指针没有同时到结尾 返回false

代码

#include 
   
    #include 
    
     #include 
     
      using namespace std;class Solution {
   public:    bool backspaceCompare(string S, string T) {
           string tmp1;        for(int i=0;i
      
       =0 || len2>=0){
               while(len1>=0){
                   if(S[len1] == '#'){
                       del1++;len1--;                }else if(del1){
                       del1--;len1--;                }else{
                       break;                }            }            while(len2>=0){
                   if(T[len2] == '#'){
                       del2++;len2--;                }else if(del2){
                       del2--;len2--;                }else{
                       break;                }            }            if(len1>=0 &&len2>=0){
                   if(S[len1] != T[len2])                    return false;            }else{
                   if(len1>=0||len2>=0)                    return false;            }            len1--;len2--;        }        return  true;    }};int main(){
       string S = "a##c";    string T = "#a#c";    Solution s;    cout<
      
     
    
   

今天也是爱zz的一天哦！

转载地址：http://cmdsn.baihongyu.com/