844. Backspace String Compare.md

844. Backspace String Compare

---

leetcode-cn Daily Challenge on October 19th, 2020.

---

Difficulty : Easy

Related Topics : Two Pointers、Stack

---

Given two strings S and T, return 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 = "#a#c"
Output: true
Explanation: Both S and T become "c".

Example 4:

Input: S = "a#c", T = "b"
Output: false
Explanation: S becomes "c" while T becomes "b".

Note:

• 1 <= S.length <= 200
• 1 <= 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?

---

Solution

• mine
  • Java

    • Runtime: 1 ms, faster than 70.07%, Memory Usage: 37.8 MB, less than 9.61% of Java online submissions

      // O(N)time
      // O(N)space
      public boolean backspaceCompare(String S, String T) {
          LinkedList<Character> listS = new LinkedList<>();
          LinkedList<Character> listT = new LinkedList<>();
          update(S, listS);
          update(T, listT);
          if(listS.size() != listT.size()) return false;
          while(!listS.isEmpty()){
              if(listS.removeLast() != listT.removeLast()) return false;
          }
          return true;
      }
      
      void update(String s, LinkedList<Character> list){
          for(char c : s.toCharArray()){
              if(c == '#'){
                  if(!list.isEmpty()) list.removeLast();
              } else list.add(c);
          }
      }
      

    • Two Pointers Runtime: 0 ms, faster than 100.00%, Memory Usage: 37.3 MB, less than 9.61% of Java online submissions

      // O(N)time
      // O(1)space
      public boolean backspaceCompare(String S, String T) {
          int p1 = S.length() - 1;
          int p2 = T.length() - 1;
          while (p1 >= 0 || p2 >= 0) {
              int count = 0;
              while (p1 >= 0 && (S.charAt(p1) == '#' || count > 0)) {
                  if (S.charAt(p1) == '#') {
                      count++;
                  } else {
                      count--;
                  }
                  p1--;
              }
              count = 0;
              while (p2 >= 0 && (T.charAt(p2) == '#' || count > 0)) {
                  if (T.charAt(p2) == '#') {
                      count++;
                  } else {
                      count--;
                  }
                  p2--;
              }
              if (p1 < 0 || p2 < 0) return p1 < 0 && p2 < 0;
      
              if (S.charAt(p1) != T.charAt(p2)) return false;
              p1--;
              p2--;
          }
          return true;
      }
      

---

• the most votes

• Two Pointers Runtime: 0 ms, faster than 100.00%, Memory Usage: 37.3 MB, less than 9.61% of Java online submissions

  // O(N)time
  // O(1)space
  public boolean backspaceCompare(String S, String T) {
      int i = S.length() - 1, j = T.length() - 1, back;
      while (true) {
          back = 0;
          while (i >= 0 && (back > 0 || S.charAt(i) == '#')) {
              back += S.charAt(i) == '#' ? 1 : -1;
              i--;
          }
          back = 0;
          while (j >= 0 && (back > 0 || T.charAt(j) == '#')) {
              back += T.charAt(j) == '#' ? 1 : -1;
              j--;
          }
          if (i >= 0 && j >= 0 && S.charAt(i) == T.charAt(j)) {
              i--;
              j--;
          } else {
              break;
          }
      }
      return i == -1 && j == -1;
  }
  

---