[leetcode #20] Valid Parentheses

Problem

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 <= 10⁴
・ s consists of parentheses only '()[]{}'.

Idea

주어진 문자열이 유효한 괄호로 구성되어있는지 확인하는 문제다.

열린 괄호는 모두 같은 형태의 괄호로 닫히는지 확인만 하면 된다. Stack을 이용하면 아주 간단하게 풀 수 있다.

우선 같은 형태의 괄호를 묶기 위해 map에 각 괄호를 key와 value로 넣어준다.

이후 문자열을 탐색하면서 현재 문자가 map의 key에 있으면 열린 괄호이므로 stack에 넣고 다음 문자를 탐색한다.

닫힌 문자가 등장하면 stack이 비어있거나 stack의 가장 위에 있는 문자가 같은 형태의 문자가 아니면 유효하지 않다고 판별할 수 있다. 이 때 stack 위 문자가 같은 형태의 문자면 해당 문자를 stack에서 제거한다.

문자열 탐색이 끝난 뒤 stack에 문자가 남아있으면 유효하지 않은 문자열이고, stack이 비어있으면 유효한 문자열이다.

Time Complexity: O(n)
Space Complexity: O(1)

Solution

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        Map<Character, Character> map = new HashMap<>();
        map.put('(', ')');
        map.put('[', ']');
        map.put('{', '}');

        for (int i=0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (map.containsKey(c)) {
                stack.push(c);
                continue;
            }
            if (stack.isEmpty()) {
                return false;
            }
            char top = stack.peek();
            if (map.get(top) != c) {
                return false;
            }
            stack.pop();
        }

        if (!stack.isEmpty()) {
            return false;
        }

        return true;
    }
}

Reference

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