Leetcode[day16] - Valid Parenthesis String

Given a string containing only three types of characters: '(', ')' and '*', write a function to check whether this string is valid. We define the validity of a string by these rules:

1. Any left parenthesis '(' must have a corresponding right parenthesis ')'.
2. Any right parenthesis ')' must have a corresponding left parenthesis '('.
3. Left parenthesis '(' must go before the corresponding right parenthesis ')'.
4. '*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string.
5. An empty string is also valid.

Input: "()"
Output: True

Input: "(*)"
Output: True

Input: "(*))"
Output: True

1. 알고리즘을 해결하기 위해서 생각한 방법

 

 - 앞에서부터 하나씩 검사하면 되지 않을까?

 - pair를 이루면 되지 않을까?

 - 양쪽에서 검사하면 되지 않을까?

 - 문제는 쉬워보였지만, 해당 문제를 깔끔하게 풀 수 있는 방법이 도저히 생각나지 않았다.

 

2. 알고리즘 작성 중, 어려운 점

 

 - 다양한 케이스를 통해서 문제를 푸는게 아닌, 문제를 풀기 위해서 일반적인 방법을 생각하는게 되지 않았다.

 

3. 유튜브 영상을 보고, 문제 풀기

 

https://www.youtube.com/watch?v=2ef4_2R4rg8

 

4. 영상을 보고 깨달은 점

 - 되는 케이스와 되지 않는 케이스를 생각해보자.

 - 되지 않는 케이스는 어떤 상황에서 되지 않는 지, 생각해보자.

 - '(' 관점과 ')' 관점에서 생각해보자.

 

5. 반성할 점

 - 어렵고, 잘 풀리지 않는 문제들이 많아지고 있다.

 - 해당 문제를 풀기위해서 오랜 시간을 투자하는 것 같은데, 명확한 답이 떠오르지 않는다.

 - 메인 아이디어를 정확하게 해야, 명확한 코드를 작성할 수 있다.

 

class Solution {
    public boolean checkValidString(String s) {
        char[] splits = s.toCharArray();
        int leftWild = 0;
        for(int i=0; i<splits.length; i++){
            if(splits[i] == ')'){
                if(leftWild == 0) return false;
                leftWild--;
            }else{
                leftWild++;
            }
        }
        
        int left = 0;
        for(int i=0; i<splits.length; i++){
            if(splits[i] == '('){
                left++;
            }else{
                left = Math.max(0, left-1);
            }
        }
        return left == 0;
    }
}

 

문제 : https://leetcode.com/explore/challenge/card/30-day-leetcoding-challenge/530/week-3/3301/

Explore - LeetCode