678. Valid Parenthesis String

문제 링크 : https://leetcode.com/problems/valid-parenthesis-string/description/

'(', ')', '' 로 이루어진 문자열이 입력값으로 주어진다.
은 '(', ')'가 될 수 있고 빈 문자도 될 수 있다.

• 가 특정 문자로 대체될 때, 괄호들의 쌍이 맞는 경우 유효한 문자열이라 한다.
  입력 문자열이 유효한 문자열인지 판단해라.

*가 열린 괄호, 닫힌 괄호,빈칸으로 대체가 가능하므로
(괄호를 +, )괄호를 -라고 할 때 최대의 수..? 최소의 수를 계산하여 true/False를 판단한다

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

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

시간복잡도는 O(n), n=s