[LeetCode 20] Valid Parentheses with JAVA

leetcode.com/problems/valid-parentheses/

Valid Parentheses - LeetCode

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.

 

Example 1:

Input: s = "()" Output: true

Example 2:

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

Example 3:

Input: s = "(]" Output: false

Example 4:

Input: s = "([)]" Output: false

Example 5:

Input: s = "{[]}" Output: true

 

Constraints:

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

 

import java.util.*;

class Solution {
    public boolean isValid(String s) {
        Stack<Character> st = new Stack<>();
        for (int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            char item;
            if (c == '(' || c == '{' || c == '[') st.push(c);
            else {
                try {
                    item = st.pop();
                } catch (EmptyStackException e){
                    return false;
                }
                if ((c == ')' && item != '(') || (c == '}' && item != '{') || (c == ']' && item != '[')){
                    return false;
                }
            }
        }
        return st.isEmpty();
    }
}

1. 어려웠던 점:

x

 

2. 알게된 점:

스택 복습

3. 알고리즘 풀이:

문자열을 첫 글자부터 마지막 글자까지 처리.

'(', '{', '[' 가 있으면 스택에 해당 글자를 push

')'가 오면 스택에서 글자를 pop해 '('가 아니면 return false

'}', ']'도 동일하다.

 

")))" 의 문자열이 오게 되면 스택이 비어 에러를 일으키므로 이 경우도 false

"(((" 의 문자열이 오게 되면 문자열을 다 처리해주어도 스택에 글자가 남기 때문에 이 경우도 false