Valid Parentheses - Getting Started / Warm Up

Problems
1

https://algo.monster/problems/valid_parentheses

2

use return dq.isEmpty() instead of ugly return (dq.isEmpty() ? true:false);

3

I think the description of the problem could be changed to specify that the input strings will only contain parentheses (either opening or closing ones.)

4

Was about to comment the same thing as Roman has, the return statement in the Java solution is needlessly verbose: Change it from return (dq.isEmpty() ? true:false); → return dq.isEmpty()

5

I would offer that the following python solution is more clear/readable than the current lesson’s solution

def valid_parentheses(s: str) → bool:
open_symbols = [“(”, “[”, “{”]
close_symbols = [“)”, “]”, “}”]
stack = []

for char in s:
    if char in open_symbols:
        stack.append(char)
    if char in close_symbols:
        mate = open_symbols[close_symbols.index(char)]
        if stack[-1] == mate:
            stack.pop()
        else:
            
            return False

return True if not stack else False
6

Easy to understand solution:

    public static boolean validParentheses(String s) {
        // WRITE YOUR BRILLIANT CODE HERE
        if (s.length() == 0) return true;
        
        Stack<Character> stack = new Stack();
        int a = 0;
        while(a<s.length()) {
            char ss = s.charAt(a);
            if (ss == '[' || ss == '{' || ss == '(') {
                stack.push(ss);
            }
            else if (ss == ')') {
                if (stack.isEmpty() || stack.pop() != '(') return false;
            }
            else if (ss == '}') {
                if (stack.isEmpty() || stack.pop() != '{') return false;
            }
            else if (ss == ']') {
                if (stack.isEmpty() || stack.pop() != '[') return false;
            }
            a++;
        }
        
        return stack.isEmpty();
    }
7

A got a similar approach but I used a different pair dictionary
`stack = []
match = {‘(’ : ‘)’,
‘[’: ‘]’,
‘{’ : ‘}’}
# Time: O(n)
# Space: O(n) since the stack can contain at most n characters
for char in s:
if char in match:
stack.append(char)
continue
else:
if stack and match[stack.pop()] != char:
return False
return True if not stack else False

8

Agreed