844 Backspace String Compare

844. Backspace String Compare

1. Question

Given two strings S andT, 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. SandTonly contain lowercase letters and'#'characters.

Follow up:

• Can you solve it inO(N)time andO(1)space?

2. Implementation

(1) Stack

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

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)