Welcome to Subscribe On Youtube

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

• Java
• C++
• Python
• Go
• TypeScript
• RenderScript

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

• 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
  
  

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

All Problems

All Solutions