20. 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

 

Constraints:

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

 

 

https://leetcode.com/problems/valid-parentheses

 

 

풀이

괄호의 열고 닫힘의 validation을 체크하는 것으로, 소/중/대 괄호에 대한 열고 닫힘이 연속되어야 하는 것이다.

(마지막에 소괄호를 열었으면 소괄호로 닫아야 한다)

이에 Stack을 이용해서 String을 char array로 변환하여 순환하면서, 열림 괄호가 나오면 Stack에 담고 닫힘 괄호가 나왔을 때 동일한 괄호가 나왔는지 확인하도록 했다.

확인하는 방법은 각 괄호에 대해 아스키 값을 확인해 보니 1 또는 2의 차이가 있는 점을 이용하여 닫힘 괄호가 나왔을 때 Stack의 pop 결과와의 차이가 1이나 2가 아닌 경우 실패로 처리했다.

 -> ( : 40, ) : 41, { : 123, } : 125, [ : 91, ] : 93

또한 String에 닫힘 괄호만 있는 등 열림 괄호가 닫힘 괄호보다 개수가 적게 있을 경우 pop할 때 Stack이 비어있기에 에러가 날 수 있다는 상황에 대한 예외 처리도 진행했다.

 

코드

class Solution {
    public boolean isValid(String s) {
        Stack<Character> valid_stack = new Stack<>();
        for(Character c : s.toCharArray()) {
        	if(c.equals('(') || c.equals('{') || c.equals('[')) {
        		valid_stack.push(c);
        	} else {
        		if(valid_stack.isEmpty()) {
        			return false;
        		}
        		char compare_c = valid_stack.pop();
        		if(c - compare_c > 2 || c - compare_c < 1) {
        			return false;
        		}
        	}
        	
        }
        
        return valid_stack.isEmpty();
    }
}

 

 

결과

Runtime : 3 ms

Memory Usage : 41.47 MB