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.

题目大意：

给定字符串S和T，其中的#表示退格

求S是否和T相等

解题思路：

栈（Stack）

Python代码：

class Solution(object):
    def backspaceCompare(self, S, T):
        """
        :type S: str
        :type T: str
        :rtype: bool
        """
        def toString(S):
            ans = []
            for c in S:
                if c == '#': ans and ans.pop()
                else: ans.append(c)
            return ''.join(ans)
        return toString(S) == toString(T)