678. Valid Parenthesis String (String, Dynamic Programming, Stack, Greedy)

링크 - https://leetcode.com/problems/valid-parenthesis-string/description/?envType=company&envId=tiktok&favoriteSlug=tiktok-thirty-days

난이도 - Medium

Intuition

1) Two Stacks

우리는 두개의 Stack을 가지고 이 문제를 풀 수 있다. 하나의 stack은 open bracket의 인덱스를 담고 다른 stack은 asterisk의 인덱스를 담는다. 그리고 ")"가 나오면 먼저 open bracket 스택을 보고 pop하고, 없으면 asterisks 스택을 보고 pop한다. 두개의 스택이 비워져 있으면 invalid하므로 False를 리턴한다.

다 끝나면 open bracket의 스택과 asterisk의 스택을 동시에 pop하면서 둘의 인덱스를 비교한다. 만약 open bracket의 인덱스 값이 더 크면, 괄호를 만들 수 없는 상황이므로 invalid하므로 False를 리턴한다.

마지막으로 open bracket 스택이 비워져있는지 여부를 답으로 반환한다.

class Solution:
    def checkValidString(self, s: str) -> bool:
        open_brackets = []
        asterisks = []

        for i, ch in enumerate(s):
            if ch == "(":
                open_brackets.append(i)
            elif ch == "*":
                asterisks.append(i)
            else:
                if open_brackets:
                    open_brackets.pop()
                elif asterisks:
                    asterisks.pop()
                else:
                    return False

        while open_brackets and asterisks:
            if open_brackets.pop() > asterisks.pop():
                return False

        return not open_brackets

Time Complexity: O(N) s를 돌면서 하기때문에 linear하게 소요된다.

Space Complexity: O(N) 각 stack에는 n개의 요소가 들어있을 수 있다.

2) Two Pointer

우리는 두개의 포인터들을 사용해서 왼쪽에서 오른쪽으로, 오른쪽에서 왼쪽으로 s의 validness를 파악할 수 있다. 

1. 왼쪽에서 오른쪽으로 가는 포인터는 각 글자가 "(" 혹은 "*"인지 보고 맞으면 1을 더한다. 아니면 1을 뺀다.

2. 오른쪽에서 왼쪽으로 가는 포인터는 각 글자가 ")" 혹은 "*"인지 보고 맞으면 1을 더한다. 아니면 1을 뺀다.

3. 이 과정중 값이 음수가 되는 순간, 이 글자는 invalid하다

class Solution:
    def checkValidString(self, s: str) -> bool:
        open_count = 0
        close_count = 0

        for i in range(len(s)):
            left, right = i, len(s) - i - 1

            if s[left] == "(" or s[left] == "*":
                open_count += 1
            else:
                open_count -= 1

            if s[right] == ")" or s[right] == "*":
                close_count += 1
            else:
                close_count -= 1

            if open_count < 0 or close_count < 0:
                return False

        return True

Time Complexity: O(N)

Space Complexity: O(1)