Question

844. Backspace String Compare

中文文档

Description

Given two strings s and t, return true _if they are equal when both are typed into empty text editors_. '#' means a backspace character.

Note that after backspacing an empty text, the text will continue empty.

 

Example 1:

Input: s = "ab#c", t = "ad#c"
Output: true
Explanation: Both s and t become "ac".

Example 2:

Input: s = "ab##", t = "c#d#"
Output: true
Explanation: Both s and t become "".

Example 3:

Input: s = "a#c", t = "b"
Output: false
Explanation: s becomes "c" while t becomes "b".

 

Constraints:

• 1 <= s.length, t.length <= 200
• s and t only contain lowercase letters and '#' characters.

 

Follow up: Can you solve it in O(n) time and O(1) space?

Solutions

Solution 1

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
  }
}