Leetcode 844. Backspace String Compare with Python

본 문서는 https://www.udemy.com/course/master-the-coding-interview-big-tech-faang-interviews/ 강의를 참조하여 작성되었습니다.

문제

Given two strings s and t, return true if they are equal when both are typed into empty text editors. '#' means a backspace character.

Note that after backspacing an empty text, the text will continue empty.

두 문자열 s와 t가 주어집니다, 문자열 내 '#'는 백스페이스의 역할을 합니다.
빈 문자열에 '#'가 주어질 경우 아무것도 일어나지 않습니다.

예시

Input: s = "ab#c", t = "ad#c"
Output: true
Explanation: s와 t 문자열 둘 다 "ac" 가 됩니다.

제한

• 1 <= s.length, t.length <= 200
• s and t only contain lowercase letters and '#' characters.

풀이법

1. MY OWN

각각의 문자열의 백스페이스를 계산하고 비교한 결과를 리턴합니다.

def backspaceCompare(s: str, t: str):
    # s 문자열의 계산
    for ch in s:
        if ch == '#' and s.index('#') != 0:
            s = s[:s.index('#')-1] + s[s.index('#')+1:]
        elif ch == '#' and s.index('#') == 0:
            s = s[:s.index('#')] + s[s.index('#')+1:]

    # t 문자열의 계산
    for ch in t:
        if ch == '#' and t.index('#') != 0:
            t = t[:t.index('#')-1] + t[t.index('#')+1:]
        elif ch == '#' and t.index('#') == 0:
            t = t[:t.index('#')] + t[t.index('#')+1:]

    # 문자열 비교
    return s == t
    

2. ANOTHER WAY

뒤에서부터 문자열을 계산해 백스페이스 문자열을 처리하고 문자 하나 하나를 비교합니다.

def backspaceCompare(s, t):
    sPointer = len(s) - 1
    tPointer = len(t) - 1
    # 백스페이스 쌓인 갯수
    sSharp = 0
    tSharp = 0
    while True:
    	# 백스페이스 문자의 처리
        if s[sPointer] == '#' and sPointer >= 0:
            sSharp += 1
            sPointer -= 1
            continue
        if sSharp != 0 and sPointer >= 0:
            sSharp -= 1
            sPointer -= 1
            continue
        if t[tPointer] == '#' and tPointer >= 0:
            tSharp += 1
            tPointer -= 1
            continue
        if tSharp != 0 and tPointer >= 0:
            tSharp -= 1
            tPointer -= 1
            continue
        if sPointer < 0 or tPointer < 0: break
        # 문자 각개 비교
        if s[sPointer] != t[tPointer]:
            return False
        else:
            sPointer -= 1
            tPointer -= 1

    if sPointer == -1 and tPointer == -1:
        return True
    else:
        return False
        

두 경우 다 시간복잡도는 O(N)이고 공간복잡도는 O(1) 입니다.