5/09/2020

[LeetCode] 20. Valid Parentheses

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

Use stack to check if the close parenthesis match with the open parenthesis.

Time complexity: O( len(s) )
Space complexity: O( len(s) )

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        Map<Character, Character> pairs = new HashMap<>() {
            {
                put('(', ')');
                put('[', ']');
                put('{', '}');
            }
        };
        
        for (char a : s.toCharArray()) {
            if (pairs.containsKey(a)) {
                stack.push(a);
            } else {
                if (stack.isEmpty() || pairs.get(stack.pop()) != a) return false;
            }
        }
        
        return stack.isEmpty();
    }
}

Edited on 03/12/2022. Use map to pair brackets.

No comments:

Post a Comment