[LeetCode] 844. Backspace String Compare 退格字符串比较

淩亂°似流年 2022-01-10 15:47 176阅读 0赞

给定 S 和 T 两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。 \# 代表退格字符。

示例 1：

输入：S = "ab\#c", T = "ad\#c"  
输出：true  
解释：S 和 T 都会变成 “ac”。

示例 2：

输入：S = "ab\#\#", T = "c\#d\#"  
输出：true  
解释：S 和 T 都会变成 “”。

示例 3：

输入：S = "a\#\#c", T = "\#a\#c"  
输出：true  
解释：S 和 T 都会变成 “c”。

示例 4：

输入：S = "a\#c", T = "b"  
输出：false  
解释：S 会变成 “c”，但 T 仍然是 “b”。

提示：

1 <= S.length <= 200  
    1 <= T.length <= 200  
    S 和 T 只含有小写字母以及字符 '\#'。

解法：用一个栈存字符，循环字符串，如果是字母就加入栈，遇到\#而且栈里面有字母就pop出栈里最后的字符。T: O(n), S:(n)

class Solution(object):
        def backspaceCompare(self, S, T):
            """
            :type S: str
            :type T: str
            :rtype: bool
            """
            s1, s2 = [], []
            for i in range(len(S)):
                if S[i] == '#' and s1:
                    s1.pop()
                elif S[i] == '#':
                    continue
                else:
                    s1.append(S[i])
    
            for j in range(len(T)):
                if T[j] == '#' and s2:
                    s2.pop()
                elif T[j] == '#':
                    continue
                else:
                    s2.append(T[j])
    
            return s1 == s2
    
    if __name__=='__main__':
        s = Solution()
        S = "ab#c"
        T = "ad#c"
        print(s.backspaceCompare(S,T))