[LC] 844. Backspace String Compare

[seungriyou]

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

Approach

Idea 1: O(n) Space

stack을 이용하여 #이 나올 때마다 pop 하는 방식으로 풀 수 있다.

Idea 2: O(1) Space (Follow-Up)

O(1) space로 풀기 위해서는 pointer를 사용하는 방식을 사용해야 한다.

이때, 다음에 유의해야 한다.

1. 어떠한 문자가 text editor에 남을지의 여부는, 해당 문자 뒤에 등장하는 backspace(#)의 개수에 달려있다.
2. 어떠한 문자 뒤에 등장하는 backspace의 개수를 세기 위해서는 뒤에서부터 거꾸로 순회해야 한다.

s와 t의 pointer를 각각 p1, p2라고 하고, 각 pointer가 가리키고 있는 문자 뒤에 등장하는 backspace 개수를 b1, b2라고 하자.

p1과 p2가 모두 0보다 작아질 때까지 다음을 반복한다.

1. s와 t의 마지막 문자에서부터 확인하면서, text editor에 남을 문자에서 멈춘다.
2. 두 문자가 서로 동일하지 않거나 문자열을 벗어난 경우라면 False를 반환한다.
3. p1, p2에서 1을 뺀다.

위 과정에서 False를 반환하지 않았다면 True를 반환한다.

while p1 >= 0 or p2 >= 0:
    # text editor에 남을 문자에서 stop
    while p1 >= 0:
        if s[p1] == "#":
            b1 += 1
            p1 -= 1
        elif b1 > 0:
            b1 -= 1
            p1 -= 1
        else:
            break
    while p2 >= 0:
        if t[p2] == "#":
            b2 += 1
            p2 -= 1
        elif b2 > 0:
            b2 -= 1
            p2 -= 1
        else:
            break

    # 동일하지 않은 경우 판단
    if (p1 < 0 and p2 >= 0) or (p1 >= 0 and p2 < 0):
        return False
    if p1 >= 0 and p2 >= 0 and s[p1] != t[p2]:
        return False

    # pointer 이동
    p1 -= 1
    p2 -= 1

return True

Complexity

• Time: O(n)
• Space: O(n) / O(1)