zhangdi

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)

ts
function backspaceCompare(s: string, t: string) {
  const backspace = (s: string) => {
    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'))

变形题 ​

题目 ​

题目

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

题解 ​

ts
function backspaceCompare2(s: string, t: string) {
  const backspace = (s: string) => {
    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 | ', backspaceCompare2('a<-b<-', 'c<-d<-'))
console.log(
  '🌰 <-<-ab<-  <-<-<-<-a  true | ',
  backspaceCompare2('<-<-ab<-', '<-<-<-<-a'),
)
console.log(
  '🌰 <-<ab<-c  <<-<a<-<-c  false | ',
  backspaceCompare2('<-<ab<-c', '<<-<a<-<-c'),
)