[1스4코2파] #267. Leetcode 678. Valid Parenthesis String

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

START :

[3코1파] 2023.01.04~ (267일차)
[4코1파] 2023.01.13~ (259일차)
[1스4코1파] 2023.04.12~ (171일차)
[1스4코2파] 2023.05.03 ~ (149일차)

Today :

2023.09.27 [267일차]

문제 설명

세 가지 유형의 문자열 '(', ')' 및 '*'만 포함하는 문자열 s가 주어질 때, 아래의 규칙을 만족하면 true를 return, 아니면 false를 return 한다.

왼쪽 괄호 '('는 오른쪽 괄호 ')'가 있어야 하고,
오른쪽 괄호 ')'에는 왼쪽 괄호 '('가 있어야 함.
왼쪽 괄호 '('는 해당 오른쪽 괄호 ')' 앞에 와야함.
'*'는 단일 오른쪽 괄호 ')' 또는 단일 왼쪽 괄호 '(' 또는 빈 문자열 ""로 생각함.

문제 풀이 방법

brute force로 푼다면 시간 복잡도는 3^n, 공간복잡도는 n^3이 나오게 됨

여는 괄호와 짝을 이루기 위해서는 해당 여는 괄호의 인덱스보다 커야하고 이를 비교해나가면서
유효한 문자열이 아닌 규칙을 넣어준다.
시간 복잡도는 O(n) 이게 됨

내 코드

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=0

        return leftMin==0   

증빙

여담

바쁘다 바빠 9월 백수 사회