LeetCode: Valid Parentheses, explanation and solution with C++/Java/Python

Valid Parentheses, explanation and solution with C++/Java/Python. This problem is easy.

Problem

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

Given a string 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. Note that an empty string is also considered valid.

Example 1:

Input: "()"
Output: true

Example 2:

Input: "()[]{}"
Output: true

Explanation

There are 3 pair of parentheses:

'(' <=> ')'
'{' <=> '}'
'[' <=> ']'

Think about the case ‘{[]}’, it is not hard to figure out, we need a Stack to store the last valid left part of parentheses, when next char is valid right part, pop out the left part.

Another trivial optimization is, any input just contains these characters, so a valid parentheses string’s length should always be even, we can add a check at the beginning.

Time complexity: $O(N)$, space complexity: $O(N)$.

The worst space complexity happened when the input similar as: ‘((((((((((‘.

C++

#include <stack>
using namespace std;

class Solution {
public:
    bool isValid(string s) {
        if(s.size()%2) return false;
        stack<char> buf;
        for(size_t i = 0; i < s.size(); i++) {
            char t = s[i];
            if(t == '(' || t == '{' || t == '[')
                buf.push(t);
            else {
                if(buf.empty()) return false;
                char p = buf.top();
                if((p == '(' && t == ')') ||
                   (p == '{' && t == '}') ||
                   (p == '[' && t == ']'))
                  buf.pop();
                else
                  return false;
            }
        }
        return buf.empty();
    }
};

Java

class Solution {
    public boolean isValid(String S) {
        if(S.length() % 2 != 0) return false;
        Stack<String> s = new Stack<String>();
        for(char c : S.toCharArray()){
            String cc = String.valueOf(c);

            if(c == '{' || c == '(' || c == '[') s.push(cc);

            else{
                if(s.empty()) return false;
                char top = s.peek().toCharArray()[0];

                if( (top == '{' && c == '}') ||
                    (top == '(' && c == ')') ||
                    (top == '[' && c == ']') ){
                    s.pop();
                } else return false;
            }

        }
        return s.empty();
    }
}

Python

For Python, we can use list replace stack, and also but a dict for clean code.

class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) % 2 != 0:
            return False
        dic = {'(' : ')', '[' : ']', '{' : '}'}
        stack = []
        g = dic.keys()
        for c in s:
            if c in dic.keys():
                stack.append(c)
            else:
                if stack == []:
                    return False
                a = stack.pop()
                if c != dic[a]:
                    return False
        return stack == []

Preparing for an interview? Checkout this!