Leetcode 844. Backspace String Compare

文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

1. Description

2. Solution

解析：Version 1，使用数据结构栈，可以解决这个问题，时间复杂度O(N)。字符每次入栈之前判断是否是星号，如果是，则栈顶元素出栈，继续下一个字符，否则入栈。这里直接变换的字符串。

• Version 1

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        return  self.backspaceString(s) == self.backspaceString(t)


    def backspaceString(self, s: str):
        res = ''
        for ch in s:
            if ch == '#':
                res = res[:-1]
            else:
                res += ch
        return res

Reference

1. https://leetcode.com/problems/backspace-string-compare/