[LeetCode] Valid Parentheses

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

Example 1:

Input: s = "()"

Output: true

Example 2:

Input: s = "()[]{}"

Output: true

Example 3:

Input: s = "(]"

Output: false

Example 4:

Input: s = "([])"

Output: true

Example 5:

Input: s = "([)]"

Output: false

 

Constraints:

• 1 <= s.length <= 104
• s consists of parentheses only '()[]{}'.

 

 

 

 

 

처음 생각했던 접근방식 (오답)

#include <stack>
#include <iostream>
#include <unordered_map>
 
using namespace std;
 
class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        unordered_map<char,char> mp;
        mp['('] = ')';
        mp['{'] = '}';
        mp['['] = ']';
 
        char cur = '\0';
        char pair = '\0';
        for(int i=0; i<s.size(); i++){
            cur = s[i];
            if(mp.find(cur) != mp.end()){
                //스택에 넣기
                st.push(cur);
            }else{
                //비교하기
                if(st.empty()) return false;
                pair = st.top();
                if(cur == mp[pair]){
                    //good
                    st.pop();
                }else{
                    return false;
                }
            }
 
        }
        return true;
    }
};
 

스택을 써서 푸는 것은 바로 떠올랐고 빠르게 구현했으나,

string s에 '{{{{' 등 close bracket이 아예 없는경우를 예외처리하지 않아서 틀렸다. 

 

 

 

 

올바른 답

#include <stack>
#include <iostream>
#include <unordered_map>
 
using namespace std;
 
class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        unordered_map<char,char> mp;
        mp['('] = ')';
        mp['{'] = '}';
        mp['['] = ']';
 
        char cur = '\0';
        char pair = '\0';
        for(int i=0; i<s.size(); i++){
            cur = s[i];
            if(mp.find(cur) != mp.end()){
                //스택에 넣기
                st.push(cur);
            }else{
                //비교하기
                if(st.empty()) return false;
                pair = st.top();
                if(cur == mp[pair]){
                    //good
                    st.pop();
                }else{
                    return false;
                }
            }
 
        }
        //수정한 부분
        if(st.empty())  return true;
        return false;
    }
};

 

마지막에 스택이 empty인지 까지 확인을 해야 옳은 정답. 항상 다양한 테스트케이스를 적용하는 연습을 해야한다.