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:

  • Open brackets must be closed by the same type of brackets.
  • Open brackets must be closed in the correct order.
  • 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

Constraints:

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

Solution

A classic stack problem.

class Solution {
    Stack<Character> st = new Stack<Character>();

    public boolean isValid(String s) {
        for (var c : s.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                st.push(c);
            } else {
                if (st.isEmpty()) {
                    return false;
                }
                var t = st.pop();
                if (c == ')' && t != '(') {
                    return false;
                } else if (c == ']' && t != '[') {
                    return false;
                } else if (c == '}' && t != '{') {
                    return false;
                }
            }
        }
        return st.isEmpty();
    }
}

Recent posts from blogs that I like

British Impressionists on the beach 2

Paintings by Philip Wilson Steer, Blanche back in Dieppe, Walter Sickert, the Bavarian son of a Danish artist and his British wife, and the Irish artist John Lavery, and more.

via The Eclectic Light Company

You learn more about writing from close reading than from writing advice

+ how David Foster Wallace creates drive in an essay

via Henrik Karlsson

How to find meaning in large tech companies

Why do many people hate working in large tech companies?

The obvious answer is “because organizational dysfunction stops them from doing the things they want to do”. Engineers like to write code and ship things, and if their company’s dysfunction is preventing that, it’ll make them unhappy. Right?

S...

via Sean Goedecke