844.Backspace-String-Compare

844. Backspace String Compare

题目地址

https://leetcode.com/problems/backspace-string-compare/

题目描述

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?

代码

Approach #1 Build String

Time: O(M + N) && Space: O(M + N)

class Solution {
  public boolean backspaceCompare(String S, String T) {
        return build(S).equals(build(T));
  }

  private String build(String S) {
    Stack<Character> ans = new Stack();
    for (char c: S.toCharArray()) {
      if (c != '#') {
        ans.push(c);
      } else if (!ans.empty()){
        ans.pop();
      }
    }
    return String.valueOf(ans);
  }
}

Approach #2 Two Pointer

public boolean backspaceCompare(String S, String T) {
  int i = S.length() - 1;
  int j = T.length() - 1;
  int 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;
}