leetcode easy : Backspace String Compare

Backspace String Compare

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

풀기 전

• #을 만나면 가장 최근에 타이핑된 문자를 지우는거니까 stack으로 표현이 가능하다.

코드 설명

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        def to_list(string):
            lst = []
            for ch in string:
                if ch == '#':
                    if lst:
                        lst.pop()
                else:
                    lst.append(ch)
            return lst
        return to_list(s) == to_list(t)

타이핑된 결과를 만들어주는 함수 to_list

주의할점은 #을 만났을 때 스택이 안 비어있는지 검사하지 않으면 런타임 에러 발생 가능

복잡도 분석

s의 길이가 n이고 t의 길이가 m일때

시간복잡도와 공간복잡도 모두 O(n+m)