844.md

844. Backspace String Compare

Leetcode link

解题思路——栈

这个题目还是比较简单的，用两个栈分别存放两个字符串，只要遇到 # 就把当前栈顶弹出去就好

C++

class Solution {
 private:
  string convert(string &S) {
    string res;
    for (char c : S) {
      if (c == '#') {
        if (!res.empty()) {
          res.pop_back();
        }
      } else {
        res += c;
      }
    }
    return res;
  }

 public:
  bool backspaceCompare(string s, string t) { return convert(s) == convert(t); }
};

Javascript

var backspaceCompare = function(s, t) {
    return convert(s) === convert(t);
};

function convert(S) {
    let res = [];
    for (let i = 0;i<S.length;i++) {
      if (S[i] == '#') {
        if (res.length !== 0) {
          res.pop();
        }
      } else {
        res.push(S[i]);
      }
    }
    return res.join('');
  }

解题思路——SC: O(1)

如果不使用栈的话可以用两个变量来 “模拟” 一下

class Solution {
 public:
  bool backspaceCompare(string s, string t) {
    int k = 0, l = 0;
    for (int i = 0; i < s.size(); i++) {
      if (s[i] == '#') {
        k = (k - 1) < 0 ? 0 : k - 1;
      } else {
        s[k] = s[i];
        k++;
      }
    }
    for (int j = 0; j < t.size(); j++) {
      if (t[j] == '#') {
        l = (l - 1) < 0 ? 0 : l - 1;
      } else {
        t[l] = t[j];
        l++;
      }
    }
    if (k != l) {
      return false;
    } else {
      for (int i = 0; i < k; i++) {
        if (s[i] != t[i]) {
          return false;
        }
      }
      return true;
    }
  }
};