# 844. 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.

**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. `1 <= S.length <= 200`
2. `1 <= T.length <= 200`
3. `S` and `T` only contain lowercase letters and `'#'` characters.

**Follow up:**

* Can you solve it in `O(N)` time and `O(1)` space?

***My Solutions:***

方法一：先处理两个string S和T，方法是用stringbuilder或者stack储存字母，碰到#就把最后一个字母删去。最后比较两个处理完的string。

Space: O(n)

```java
public boolean backspaceCompare(String S, String T) {
    if (S.length() == 0 && T.length() == 0) return true;
    String s = convert(S);
    String t = convert(T);
    return s.equals(t);
}

public String convert(String str) {
    StringBuilder sb = new StringBuilder();
    for (char c : str.toCharArray()) {
        if (c == '#') {
            if (sb.length() == 0) continue; // 没有字母可以删，do nothing
            else sb.setLength(sb.length() - 1); // remove last char
        } else {
            sb.append(c);
        }
    }
    return sb.toString();
}
```

方法2：用两个pointer标记从string的末尾往前走，S和T会被保留的字母的index。然后比较这个index上S和T的字母是否相同，直到index<0。

Space: O(1)

```java
public boolean backspaceCompare(String S, String T) {
    int s = S.length() - 1, t = T.length() - 1;
    while (s >= 0 || t >= 0) {
        s = moveBack(S, s);
        t = moveBack(T, t);
        if (s >= 0 && t >= 0 && S.charAt(s) != T.charAt(t)) return false;
        if (s < 0 || t < 0) return s == t;
        s--;
        t--;
    }
    return true;
}

public int moveBack(String str, int index) {
    int count = 0; // count how many chars need to be deleted
    while (index >= 0) {
        if (str.charAt(index) == '#') {
            count++;
            index--;
        } else if (count > 0) {
            count--;
            index--;
        } else {
            return index;
        }
    }
    return index;
}
```