[2024] day 99. Leetcode 678. Valid Parenthesis String

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 4월 7일 (일)
Leetcode daily problem

678. Valid Parenthesis String

https://leetcode.com/problems/valid-parenthesis-string/?envType=daily-question&envId=2024-04-07

Problem

'(', ')', '*' 3개의 문자로만 이루어진 문자열이 유효한 괄호 형식을 띄고 있으면 True, 아니면 False를 반환한다.

- '('는 ')'보다 왼쪽에 있어야함
- ')'는 '('보다 오른쪽에 있어야함
- '*'는 '(' 와 ')' 가운데, 사이에 있어야 함

'*'는 와일드 카드 이다.

Solution

two pointer

해당 방법은 다이나믹 프로그래밍, 스택, 투 포인터등 여러가지 방법으로 해결할 수 있다.
투 포인터로 해결하는 방법은

여는 괄호와 닫는 괄호를 초기화해서 해당 괄호의 수를 업데이트해가면서 추적하는 것이다. 입력 문자열 s의 길이를 계산하여 길이변수에 할당한다.

단일 루프를 사용하여 문자열을 양쪽 끝에서 동시에 탐색한다.
0부터 길이(포함)까지 인덱스 i를 반복하는데,

• 인덱스 i의 문자가 (또는 *인 경우 openCount를 증가시킨다.
  그렇지 않으면 openCount를 감소시킨다.
• 인덱스 길이 - i의 문자가 ) 또는 *인 경우 closeCount를 증가킨다.
  그렇지 않으면 closeCount를 감소시킵니다.
  루프 중 어느 시점에서든 여는 괄호나 닫는괄호가 음수로 변하는 경우 이는 여는 괄호(또는 별표)보다 닫는 괄호가 더 많다는 의미이므로 문자열이 유효하지 않게 된다. 이 경우 false를 반환한다.
  루프가 반환 없이 전체 문자열 순회를 마친 후 여는 괄호나 닫는괄호가 음수가 아니라면 즉, 문자열이 유효하다는 의미이므로 true를 반환한다.

Code

class Solution:
    def checkValidString(self, s: str) -> bool:
        Open, Close = 0, 0
        length = len(s)-1
        
        for i in range(length+1):
            if s[i] == '(' or s[i] == '*':
                Open +=1
            else:
                Open -=1
            
            if s[length-i] == ')' or s[length-i] == '*':
                Close +=1
            
            else:
                Close -=1
                
            
            if Open < 0 or Close <0:
                return False
        
        return True

Complexicity

시간 복잡도

입력 문자열의을 왼쪽부터 오른쪽으로 한 번씩 스킨해므로, 입력 문자열의 길이에 비례하는 선형 시간이 소요된다. 해당 코드의 시간 복잡도는 O(n)이다.

공간 복잡도

주어진 문자열 외에 상수 개수의 변수만 사용하므로 해당 코드의 공간 복잡도는 O(n)이다.