844.Backspace String Compare

Tags: Easy String

Links: 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.

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?

---

class Solution {
public:
    bool backspaceCompare(string S, string T) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        bakcSpace(S); bakcSpace(T);
        return S == T;
    }

    void bakcSpace(string & s)
    {
        int n = s.size();
        int pos = -1;
        int capacity = 0;
        for (int i = 0; i < n; ++i) {
            if (s[i] == '#') {
                if (capacity) {
                    --capacity;
                    --pos;
                }
            }
            else {
                s[++pos] = s[i];
                ++capacity;
            }
        }
        s = s.substr(0, pos + 1);        
    }
};

用capacity和pos模拟栈，注意这里pos代表栈底端的元素位置，这样方便处理。