zhangdizhangdi

844.比较含退格的字符串

LeetCode 原题

题目

LeetCode 简单

题目

给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。

示例：
输入：s = “ab#c”, t = “ad#c”
输出：true
解释：s 和 t 都会变成 “ac”。

输入：s = “ab##”, t = “c#d#”
输出：true
解释：s 和 t 都会变成 “”。

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

题解

栈 O(N+M) O(N+M)

js
function backspaceCompare(s, t) {
  const backspace = s => {
    const stack = []
    const len = s.length
    for (let i = 0; i < len; i++) {
      const char = s[i]
      if (char === '#') {
        if (stack.length > 0) {
          stack.pop()
        }
      } else {
        stack.push(char)
      }
    }
    return stack.join('')
  }

  return backspace(s) === backspace(t)
}

console.log('🌰 ab#c ad#c true | ', backspaceCompare('ab#c', 'ad#c'))
console.log('🌰 ab## c#d# true | ', backspaceCompare('ab##', 'c#d#'))
console.log('🌰 a#c b# false | ', backspaceCompare('a#c', 'b'))
执行结果
🌰 ab#c ad#c true |  true
🌰 ab## c#d# true |  true
🌰 a#c b# false |  false

变形题

题目

题目

遇到退格字符就删除前面的字符, 遇到两个退格就删除两个字符
比较含有退格的字符串，“<-“代表退格键，”<“和”-“均为正常字符
输入：“a<-b<-”, “c<-d<-”，结果：true，解释：都为””
输入：“<-<-ab<-”, “<-<-<-<-a”，结果：true，解释：都为"a"
输入：“<-<ab<-c”, “<<-<a<-<-c”，结果：false，解释：“<ac” !== “c”

题解

js
function backspaceCompare(s, t) {
  const backspace = s => {
    const stack = []
    const len = s.length
    for (let i = 0; i < len; i++) {
      const char = s[i]
      if (char === '-') {
        //先将前一个字符弹出
        const prevChar = stack.pop()
        if (prevChar === '<') {
          //如果与前一个字符组成退格键，删除最后一个字符
          if (stack.length > 0) {
            stack.pop()
          }
        } else {
          //不能组成退格键，push两个字符到stack
          stack.push(prevChar)
          stack.push(char)
        }
      } else {
        stack.push(char)
      }
    }
    return stack.join('')
  }

  return backspace(s) === backspace(t)
}

console.log('🌰 a<-b<-  c<-d<-  true | ', backspaceCompare('a<-b<-', 'c<-d<-'))
console.log(
  '🌰 <-<-ab<-  <-<-<-<-a  true | ',
  backspaceCompare('<-<-ab<-', '<-<-<-<-a'),
)
// console.log(
//   '🌰 <-<ab<-c  <<-<a<-<-c  false | ',
//   backspaceCompare('<-<ab<-c', '<<-<a<-<-c'),
// )
执行结果
🌰 a<-b<-  c<-d<-  true |  true
🌰 <-<-ab<-  <-<-<-<-a  true |  true