[DSA][Greedy] 08. Valid Parenthesis String

LeetCode 678

 

08. Valid Parenthesis String

Given a string s containing only three types of characters: '(', ')' and '*', return true if s is valid.

The following rules define a valid string:
Any left parenthesis '(' must have a corresponding right parenthesis ')'.
Any right parenthesis ')' must have a corresponding left parenthesis '('.
Left parenthesis '(' must go before the corresponding right parenthesis ')'.
'*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string "".

 

 

[아이디어]

- *를 '(', ')', 또는 빈 문자열로 해석할 수 있으므로, 가능한 열린 괄호 개수의 최솟값과 최댓값을 동시에 추적한다.

 

 

[풀이 1] Greedy

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

        for c in s:
            if c == "(":
                leftMin, leftMax = leftMin + 1, leftMax + 1
            elif c == ")":
                leftMin, leftMax = leftMin - 1, leftMax - 1
            else:
                leftMin, leftMax = leftMin - 1, leftMax + 1
            if leftMax < 0:
                return False
            if leftMin < 0:
                leftMin += 1 
        return leftMin == 0

'*' 문자는 '(', ')', 또는 빈 문자열 ''로 해석될 수 있기 때문에, 모든 경우의 수를 고려하면 시간 복잡도가 최대 3^n으로 폭발적으로 증가한다.

따라서 모든 조합을 직접 탐색하는 대신, 현재까지 유효할 수 있는 열린 괄호 개수의 최소값(leftMin)과 최댓값(leftMax)을 동시에 관리하는 방식으로 문제를 해결한다.

• '(' 문자가 나오면 열린 괄호가 하나 추가되므로 leftMin과 leftMax 모두 +1 증가시킨다.
• ')' 문자가 나오면 열린 괄호가 하나 닫히므로 leftMin과 leftMax 모두 -1 감소시킨다.
• '*' 문자는 세 가지 역할이 가능하므로 닫는 괄호로 해석할 때 최소값은  -1, 여는 괄호로 해석할 때 최댓값은 +1을 적용한다.

leftMax가 음수가 되는 경우는 닫는 괄호가 여는 괄호보다 많아져 어떤 해석으로도 유효할 수 없는 상황이므로 바로 False를 반환한다. 한편, leftMin이 음수가 되었다면 닫는 괄호가 너무 많았다는 뜻이지만, *를 빈 문자열로 해석하거나 (로 해석하면 그 상황을 보정할 수 있으므로 leftMin을 +1 해준다. 모든 문자를 처리한 뒤 leftMin == 0이라면 적어도 하나의 해석에서 모든 괄호가 올바르게 짝을 이룬 경우가 존재하므로 문자열은 유효하다고 판단한다.

leftMin이 음수가 되었는데 leftMax는 음수가 아니라면, 닫는 괄호가 아닌 *가 있었다는 의미이고 *를 다시 '('로 해석해 주기 위해 leftMin에 1을 더해준다.

 

⏱️ 시간복잡도

문자열을 한 번만 순회하므로 시간 복잡도는 O(n)이다.

🧠 공간복잡도

두 변수만을 사용하므로 공간 복잡도는 O(1)이다.