# 844     Backspace String Compare

## 844. [Backspace String Compare](https://leetcode.com/problems/backspace-string-compare/description/)

## 1. Question

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?

## 2. Implementation

**(1) Stack**

思路: 用StringBuilder模拟stack的操作，当遇到"#"而且stringbuilder不为空时，将最后一个character删除

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

    public String getString(String s) {
        StringBuilder res = new StringBuilder();

        for (char c : s.toCharArray()) {
            if (c != '#') {
                res.append(c);
            }
            else if (res.length() > 0) {
                res.deleteCharAt(res.length() - 1);
            }
        }
        return res.toString();
    }
}
```

## 3. Time & Space Complexity

**(1) Stack：** 时间复杂度O(n), 空间复杂度O(1)