[LeetCode] 678. Valid Parenthesis String

https://leetcode.com/problems/valid-parenthesis-string/submissions/1225282138/

Leetcode - Valid Parenthesis String

문제 유형 : 문자열 처리, 스택

문제 난이도 : Medium

 

문제

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 "".

 

문자열 s가 주어지는데, '(', ')', '*' 으로만 이루어진다. 이게 유효한 문자열인지 확인하시오.

 

다음의 규칙을 지켜야 합니다:

• 왼쪽의 괄호 '('는 오른쪽에 상응하는 ')'가 있어야 합니다.
• 오른쪽의 괄호 ')'는 왼쪽에 상승하는 '('가 있어야 합니다.
• '*'는 '(', ')', 또는 빈 문자열 ""로 인정됩니다.

 

풀이

어제의 문제(https://riveroverflow.tistory.com/entry/LeetCode-1249-Minimum-Remove-to-Make-Valid-Parentheses)

와 비슷하다.

 

문자열을 정방향으로 순회하면서, 유효한 여는 괄호의 수를 체킹한다. 여기서, 별표도 인정시킨다.

순회 중, 만약 닫는 괄호가 여는 괄호의 숫자보다 많아진다면, false를 반환한다.

 

역방향으로 순회하면, 닫는 괄호가 여는 괄호가 된다. 역방향의 순회를 스택으로 할 수도 있고, 그냥 반복문을 거꾸로 돌려도 된다.

똑같이 순회하면서 체킹한다.

 

중간 과정에서 false 반환이 없다면, 유효한 문자열이다. 어차피 별표시는 빈 문자열로 바뀔 수 있기 때문에, 남은 별 표시가 얼마든 상관없다.

 

코드

C++

class Solution {
public:
    bool checkValidString(string s) {
        stack<char> st;
        int ableOpening = 0;

        for(const char ch : s) {
            if(ch == '(' || ch == '*') ableOpening++;
            else if(ch == ')') {
                if(ableOpening == 0) return false;
                ableOpening--;
            }
            st.push(ch);
        }

        ableOpening = 0;
        while(!st.empty()) {
            char ch = st.top();
            st.pop();

            if(ch == ')' || ch == '*') ableOpening++;
            else if(ch == '(') {
                if(ableOpening == 0) return false;
                ableOpening--;
            }
        }

        return true;
    }
};