Minimum Add to Make Parentheses Valid[M,String,Stack,Greedy]

https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/description/?envType=daily-question&envId=2024-10-09

A parentheses string is valid if and only if:

• It is the empty string,
• It can be written as AB (A concatenated with B), where A and B are valid strings, or
• It can be written as (A), where A is a valid string.

You are given a parentheses string s. In one move, you can insert a parenthesis at any position of the string.

• For example, if s = "()))", you can insert an opening parenthesis to be "(()))" or a closing parenthesis to be "())))".

Return the minimum number of moves required to make s valid.

 

Example 1:

Input: s = "())"
Output: 1

Example 2:

Input: s = "((("
Output: 3

 

Constraints:

• 1 <= s.length <= 1000
• s[i] is either '(' or ')'.

 

1. Python

 

최근에 괄호 문제를 좀 풀어서 그런가 ㅋㅋ;

가볍게 풀어냈다. 자만은 금지다. 애초에 leetscode는 문제 TOPIC을 제시해주어서, 사실 이것만해도 큰 힌트가 된다.

class Solution:
    def minAddToMakeValid(self, s: str) -> int:
        ans = 0
        lst = deque()
        for x in s :
            if x ==')' :
                if not lst :
                    ans +=1
                    continue
                if lst[-1] == '(':
                    lst.pop()
            else : lst.append(x)
        return ans + len(lst)

 

 

2. C

C 특성상 Container를 만들기 귀찮은데, 그걸 해결하는 아이디어다.

꽤나 괜찮은 아이디어인듯!

int minAddToMakeValid(char* s) {
    int open = 0;
    int close = 0;
    int n = strlen(s);

    for(int i=0;i<n;i++){
        if(s[i]=='('){
            open++;
        }
        else{
            if(open>0){
                open--;
            }
            else close++;
        }
    }
    return open+close;
}

 

 

3. C++

class Solution {
public:
    int minAddToMakeValid(string s) {
        stack<char> S;
        int ans=0;
        for(char ch : s){
            if(ch==')'){
                if(S.empty()) ans++;
                else S.pop();
            }
            else{
                S.push(ch);
            }
        }
        return ans+S.size();
    }
};