•
문제 설명 : 텍스트 에디터에서 입력한 문자를 s, t 로 전달한다. 이때 결과가 동일한지 반환한다.
•
풀이 방법
◦
스택 방식을 사용하여 진행하였다.
▪
다만 이 방법은 공간 복잡도가 O(1) 이 아니기 때문에, 공간 복잡도를 O(1) 로 줄일 수 있는 방법을 찾아보았다.
•
시간복잡도 :
•
성공 코드
class Solution:
def backspaceCompare(self, s: str, t: str) -> bool:
s_info = []
t_info = []
for s_ch in s:
if s_ch == '#' and s_info:
s_info.pop()
elif s_ch != '#':
s_info.append(s_ch)
for t_ch in t:
if t_ch == '#' and t_info:
t_info.pop()
elif t_ch != '#':
t_info.append(t_ch)
return s_info == t_info
Python
복사
•
성공 코드 (공간 복잡도 O(1) 개선)
뒤에서부터 확인하는 방식을 선택하였다.
추가적으로 제너레이터를 사용하여 이터레이터를 만드는 방식을 사용하였는데, 이 방법도 자주 사용해봐야겠다.
class Solution:
def backspaceCompare(self, s: str, t: str) -> bool:
def process_string(string):
skip = 0
for char in reversed(string):
if char == '#':
skip += 1
elif skip > 0:
skip -= 1
else:
yield char
return all(x == y for x, y in zip(process_string(s), process_string(t)))
Python
복사