20. Valid Parentheses

Easy

 

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

 

Constraints:

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

 

풀이방법

 

Stack을 사용해서 해당문제를 해결함

1.  '(' , '{', '[' 문자가 입력되면 Stack에 해당 글자를 push함

2.  ')' , '}' , ']' 가 오면 Stack에서 괄호를 pop한다. 

3. for문을 돌면서 현재 문자와 Stack에서 추출한 문자가 모두 한 괄호의 쌍인지 확인한다.

   즉, 괄호의 쌍은 

   1) '(' , ')' 

   2) '{', '}' 

   3)  '[', ']'

이렇게 3가지 케이스만 가능함.

4. for문 순회를 마치고 Stack이 모두 비어있으면 true 임!

 

false 케이스

- Stack에서 pop하는데 Stack이 빈 경우에는 괄호의 열고 닫는 쌍이 서로 맞지 않는것을 의미하므로 false

- 괄호의 쌍이 3번 케이스가 아닌경우, 예를 들면 열고 닫는 괄호들이 '(' , '}' 처럼 서로 모양이 맞지 않는 경우를 의미함.

 

Source Code

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