Question

844. 比较含退格的字符串

English Version

题目描述

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

注意：如果对空文本输入退格字符，文本继续为空。

 

示例 1：

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

示例 2：

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

示例 3：

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

 

提示：

• 1 <= s.length, t.length <= 200
• s 和 t 只含有小写字母以及字符 '#'

 

进阶：

• 你可以用 O(n) 的时间复杂度和 O(1) 的空间复杂度解决该问题吗？

解法

方法一：双指针

我们用双指针 $i$ 和 $j$ 分别指向字符串 $s$ 和 $t$ 的末尾。

每次向前移动一个字符，如果当前字符是退格符，则跳过当前字符，同时退格符的数量加一，如果当前字符不是退格符，则判断退格符的数量，如果退格符的数量大于 $0$，则跳过当前字符，同时退格符的数量减一，如果退格符的数量等于 $0$，那么该字符需要进行比较。

我们每次找到两个字符串中需要比较的字符，然后进行比较，如果两个字符不相等，则返回 $false$，如果遍历完两个字符串，都没有发现不相等的字符，则返回 $true$。

时间复杂度 $O(m + n)$，空间复杂度 $O(1)$。其中 $m$ 和 $n$ 分别是字符串 $s$ 和 $t$ 的长度。

class Solution:
  def backspaceCompare(self, s: str, t: str) -> bool:
    i, j, skip1, skip2 = len(s) - 1, len(t) - 1, 0, 0
    while i >= 0 or j >= 0:
      while i >= 0:
        if s[i] == '#':
          skip1 += 1
          i -= 1
        elif skip1:
          skip1 -= 1
          i -= 1
        else:
          break
      while j >= 0:
        if t[j] == '#':
          skip2 += 1
          j -= 1
        elif skip2:
          skip2 -= 1
          j -= 1
        else:
          break
      if i >= 0 and j >= 0:
        if s[i] != t[j]:
          return False
      elif i >= 0 or j >= 0:
        return False
      i, j = i - 1, j - 1
    return True

class Solution {
  public boolean backspaceCompare(String s, String t) {
    int i = s.length() - 1, j = t.length() - 1;
    int skip1 = 0, skip2 = 0;
    for (; i >= 0 || j >= 0; --i, --j) {
      while (i >= 0) {
        if (s.charAt(i) == '#') {
          ++skip1;
          --i;
        } else if (skip1 > 0) {
          --skip1;
          --i;
        } else {
          break;
        }
      }
      while (j >= 0) {
        if (t.charAt(j) == '#') {
          ++skip2;
          --j;
        } else if (skip2 > 0) {
          --skip2;
          --j;
        } else {
          break;
        }
      }
      if (i >= 0 && j >= 0) {
        if (s.charAt(i) != t.charAt(j)) {
          return false;
        }
      } else if (i >= 0 || j >= 0) {
        return false;
      }
    }
    return true;
  }
}

class Solution {
public:
  bool backspaceCompare(string s, string t) {
    int i = s.size() - 1, j = t.size() - 1;
    int skip1 = 0, skip2 = 0;
    for (; i >= 0 || j >= 0; --i, --j) {
      while (i >= 0) {
        if (s[i] == '#') {
          ++skip1;
          --i;
        } else if (skip1) {
          --skip1;
          --i;
        } else
          break;
      }
      while (j >= 0) {
        if (t[j] == '#') {
          ++skip2;
          --j;
        } else if (skip2) {
          --skip2;
          --j;
        } else
          break;
      }
      if (i >= 0 && j >= 0) {
        if (s[i] != t[j]) return false;
      } else if (i >= 0 || j >= 0)
        return false;
    }
    return true;
  }
};

func backspaceCompare(s string, t string) bool {
  i, j := len(s)-1, len(t)-1
  skip1, skip2 := 0, 0
  for ; i >= 0 || j >= 0; i, j = i-1, j-1 {
    for i >= 0 {
      if s[i] == '#' {
        skip1++
        i--
      } else if skip1 > 0 {
        skip1--
        i--
      } else {
        break
      }
    }
    for j >= 0 {
      if t[j] == '#' {
        skip2++
        j--
      } else if skip2 > 0 {
        skip2--
        j--
      } else {
        break
      }
    }
    if i >= 0 && j >= 0 {
      if s[i] != t[j] {
        return false
      }
    } else if i >= 0 || j >= 0 {
      return false
    }
  }
  return true
}

function backspaceCompare(s: string, t: string): boolean {
  let i = s.length - 1;
  let j = t.length - 1;
  while (i >= 0 || j >= 0) {
    let skip = 0;
    while (i >= 0) {
      if (s[i] === '#') {
        skip++;
      } else if (skip !== 0) {
        skip--;
      } else {
        break;
      }
      i--;
    }
    skip = 0;
    while (j >= 0) {
      if (t[j] === '#') {
        skip++;
      } else if (skip !== 0) {
        skip--;
      } else {
        break;
      }
      j--;
    }
    if (s[i] !== t[j]) {
      return false;
    }
    i--;
    j--;
  }
  return true;
}

impl Solution {
  pub fn backspace_compare(s: String, t: String) -> bool {
    let (s, t) = (s.as_bytes(), t.as_bytes());
    let (mut i, mut j) = (s.len(), t.len());
    while i != 0 || j != 0 {
      let mut skip = 0;
      while i != 0 {
        if s[i - 1] == b'#' {
          skip += 1;
        } else if skip != 0 {
          skip -= 1;
        } else {
          break;
        }
        i -= 1;
      }
      skip = 0;
      while j != 0 {
        if t[j - 1] == b'#' {
          skip += 1;
        } else if skip != 0 {
          skip -= 1;
        } else {
          break;
        }
        j -= 1;
      }
      if i == 0 && j == 0 {
        break;
      }
      if i == 0 || j == 0 {
        return false;
      }
      if s[i - 1] != t[j - 1] {
        return false;
      }
      i -= 1;
      j -= 1;
    }
    true
  }
}