678. Valid Parenthesis String

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

 

원래는 스택을 써서 풀어야 하는 것 같은 문제인데, 조건 하나가 더 추가된 문제. 괄호 (, ) 외에도 아스터리스크 *가 문자열에 포함된다. 조커처럼 (, ) 또는 공백으로 사용될 수 있고, 이런 상황에서 주어진 문자열이 vaild한지 체크하면 된다.

 

애스터리스크가 어떻게 사용될 수 있을지 모르기 때문에, 매 시점에서 가능한 여는 괄호가 나오면 1 커지고, 닫는 괄호가 나오면 1 작아지는 변수 l_p, r_p를 만들어두고, 애스터리스크가 나오면 l_p는 -1, r_p는 +1을 해준다. l_p, r_p가 각각 여는 괄호가 짝이 지어진 괄호를 제외하고 가질 수 있는 최솟값/최댓값을 가진다고 생각하면 된다.

 

r_p가 0보다 작아지는 구간이 하나라도 생기면 무조건 not vaild한 문자열이다.[모든 *을 (로 사용해도 불가능], 반대로 l_p가 0보다 작아지는 구간이 발생하더라도 0으로 둔다. 최솟값이 0이 될 수는 없기 때문이다.

 

모든 짝이 지어졌다면 l_p가 0이 나와야 하는데, 그렇지 못한다면 not vaild하다고 생각할 수 있다.

 

	class Solution:
	def checkValidString(self, s: str) -> bool:
	l_p, r_p = 0, 0
	for c in s:
	if c == "(":
	l_p += 1
	r_p += 1
	elif c == ")":
	l_p -= 1
	r_p -= 1
	else:
	l_p -= 1
	r_p += 1
	if r_p < 0:
	return False
	l_p = max(l_p, 0)
	return l_p == 0

view raw Valid Parenthesis String.py hosted with ❤ by GitHub