[844. Backspace String Compare]

(https://leetcode.cn/problems/backspace-string-compare/)

栈

• 此题一看就有一股浓浓的栈味儿，毕竟匹配问题可是栈的强项

• 使用字符串string作为栈，末尾添加和弹出，最后只需比较两个字符串即可，比栈方便点

  class Solution {
  public:
      bool backspaceCompare(string S, string T) {
          string s; 
          string t; 
          
          for (int i = 0; i < S.size(); i++) {
              if (S[i] != '#') s += S[i];
              else if ( s.empty() == false ) s.pop_back();
          }
              
          for (int i = 0; i < T.size(); i++) {
              if (T[i] != '#') t += T[i];
              else if ( t.empty() == false ) t.pop_back();
  
          }
          
          if (s == t) return true; 
          
          return false;
      }
  };
  

• 时间复杂度:O(n + m)

• 空间复杂度:O(n + m)

双指针法

• 很显然，栈的空间复杂度没法做到O(1)，是数组且需要原地操作，很容易想到双指针法来进行删除

• 此题，一个字符是否会被删掉，只取决于该字符后面的退格符，因此我们需要逆序进行操作

• 具体做法：我们需要定义s,t的最大下标sIndex和tIndex，以及记录s中'#'数量的sSharpNums和记录t中'#'数量的tSharpNums

  • 两个字符串同时移动，每次移动时，我们需要看当前是否为'#'或'#'数量是否大于0 ，是就继续走，不是就进行比较，若目标值不同则return false
  • 数组越界则终止移动，随后判断两个字符串移动的索引是否都小于0，若是则return false

• 实现：

  class Solution {
  public:
      bool backspaceCompare(string s, string t) {
          
          int sIndex = s.size() - 1, tIndex = t.size() - 1;
          int sSharpNums = 0, tSharpNums = 0;
  
          while( true )
          {
              
              //是否为'#'或'#'数量是否大于0，消耗#
              while( sIndex >= 0 )
              {
                  if( s[sIndex] == '#' ) sSharpNums++;
                  else
                  {
                      if( sSharpNums > 0 ) --sSharpNums;
                      else break;
                  }
                  --sIndex;
              }
  
              while( tIndex >= 0 )
              {
                  if( t[tIndex] == '#' ) tSharpNums++;
                  else
                  {
                      if( tSharpNums > 0 ) --tSharpNums;
                      else break;
                  }
                  --tIndex;
              }
  
              //越界终止
              if( sIndex < 0 || tIndex < 0 ) break;
  
              //目标值不同则终止
              if( s[sIndex] != t[tIndex] ) return false;
  
              --sIndex, --tIndex;
          }
  
          if( sIndex < 0 && tIndex < 0 ) return true;
  
          return false;
      }
  };
  

• 时间复杂度：O(n + m)

  空间复杂度：O(1)