/*
 * [844] 比较含退格的字符串
 */

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var backspaceCompare = function (s, t) {
  // 1. 采用快慢指针
  // function backspace(str) {
  //   str = str.split('');
  //   let short = 0;
  //   for (let fast = 0; fast < str.length; fast++) {
  //     if (str[fast] !== '#') {
  //       [str[short], str[fast]] = [str[fast], str[short]];
  //       short++
  //     } else {
  //       short = short > 0 ? short - 1 : 0
  //     }
  //   }
  //   return str.slice(0, short).join('')
  // }

  // return backspace(s) === backspace(t)

  // 2. 使用栈
  function backspace(str) {
    let stack = []
    for (let i = 0; i < str.length; i++) {
      if (str[i] !== '#') {
        stack.push(str[i])
      } else {
        stack.pop()
      }
    }
    return stack.join('')
  }
  return backspace(s) === backspace(t)
};

console.log(backspaceCompare('ab#c', 'ad#c'))
console.log(backspaceCompare('ab##', 'c#d#'))
console.log(backspaceCompare('a#c', 'b'))
console.log(backspaceCompare('y#fo##f', 'y#f#o##f'))