Leetcode 20. Valid Parentheses

Problem Explanation

This problem is asking us to check if the parentheses in a given string are valid or not. In order for the parentheses to be valid, every opening bracket ("(", "{", "[") should be closed by its corresponding closing bracket (")", "}", "]") and should be in correct order. If there is a mismatch in these conditions, the string is considered to be invalid. The problem makes an assumption that any empty string is considered as valid.

For example, given the string "()", it is valid because every open bracket is closed.

On the other hand, given the string, "{[}", this would be invalid. Although all the open brackets are closed, they are closed by different types of brackets.

Finally, given the string "{[()]}" this is valid as all open brackets are not only closed, but are also closed in the correct order.

The approach for this solution checks for these two conditions - if the brackets are closed and if they are closed in the correct order.

Algorithm Walkthrough

The algorithm used in this solution is Stack data structure. The main concept of Stack data structure is "LIFO - Last In First Out". Meaning, the last element added to the stack will be the first one to be removed.

We iterate over the given string from left to right, adding an element to the stack every time we find an open bracket and removing the top element from the stack every time we find a close bracket. Every time we add an element to the stack, we also record what its closing bracket should be.

Here's a step by step run of this algorithm on the string "{()}[]":

As we can see, for every opening bracket we meet, we add the closing bracket onto the top of the stack. When we encounter a closing bracket, if the stack is not empty and the top of the stack is the same as the closing bracket, we pop from the stack. If either the stack is empty or the top of the stack is not the same as the closing bracket we are looking at, we return false. If we finish iterating through the string, and the stack is empty, we return true.

Python Solution

1
2python
3class Solution:
4    def isValid(self, s):
5        stack = []
6        map = {
7            "(": ")",
8            "{": "}",
9            "[": "]"
10        }
11        for char in s:
12            if char in map:
13                stack.append(map[char])
14            elif not stack or char != stack.pop():
15                return False
16        return not stack

Java Solution

1
2java
3import java.util.Stack;
4
5class Solution {
6    public boolean isValid(String s) {
7        Stack<Character> stack = new Stack<>();
8        for (char c : s.toCharArray()) {
9            if (c == '(')
10                stack.push(')');
11            else if (c == '{')
12                stack.push('}');
13            else if (c == '[')
14                stack.push(']');
15            else if (stack.isEmpty() || stack.pop() != c)
16                return false;
17        }
18        return stack.isEmpty();
19    }
20}

JavaScript Solution

1
2javascript
3const isValid = (s) => {
4    const stack = [];
5    const map = {
6        '(': ')',
7        '[': ']',
8        '{': '}'
9    }
10    for (let char of s) {
11        if (map[char]) {
12            stack.push(map[char]);
13        } else if (char !== stack.pop()) {
14            return false;
15        }
16    }
17    return !stack.length;
18}

C++ Solution

1
2cpp
3class Solution {
4public:
5    bool isValid(string s) {
6        stack<char> my_stack;
7        for (char c : s) {
8            if (c == '(')
9                my_stack.push(')');
10            else if (c == '{')
11                my_stack.push('}');
12            else if (c == '[')
13                my_stack.push(']');
14            else if (my_stack.empty() || my_stack.top() != c)
15                return false;
16            else
17                my_stack.pop();
18        }
19        return my_stack.empty();
20    }
21};

C# Solution

1
2csharp
3public class Solution {
4    public bool IsValid(string s) {
5        Stack<char> my_stack = new Stack<char>();
6
7        foreach(var c in s)
8            switch (c)
9            {
10                case '(':
11                    my_stack.Push(')');
12                    break;
13                case '{':
14                    my_stack.Push('}');
15                    break;
16                case '[':
17                    my_stack.Push(']');
18                    break;
19                default:
20                    if (!my_stack.Any() || my_stack.Pop() != c)
21                        return false;
22                    break;
23            }
24
25        return !my_stack.Any();
26    }
27}

In all of the above solutions, we first create an empty stack. As we iterate through the input string, we push the corresponding closing bracket onto the stack whenever we encounter an opening bracket. If we encounter a closing bracket, we check if the stack is empty or if the top element of the stack is not equal to the closing bracket. If either condition is true, we return false because the parentheses are not balanced. If we have finished iterating through the string and the stack is empty, we return true indicating the parentheses are balanced.## Swift Solution

1
2swift
3class Solution {
4    func isValid(_ s: String) -> Bool {
5        var stack = [Character]()
6        let map: [Character:Character] = ["(":")", "{":"}", "[":"]"]
7        
8        for char in s {
9            if map.keys.contains(char) {
10                stack.append(map[char]!)
11            } else if stack.isEmpty || char != stack.removeLast() {
12                return false
13            }
14        }
15        return stack.isEmpty
16    }
17}

Ruby Solution

1
2ruby
3def is_valid(s)
4    stack = []
5    map = { "(" => ")", "{" => "}", "[" => "]" }
6    s.each_char do |char|
7        if map.keys.include?(char)
8            stack << map[char]
9        else
10            return false if stack.empty? || char != stack.pop
11        end
12    end
13    stack.empty?
14end

Go Solution

1
2go
3func isValid(s string) bool {
4    stack := make([]rune, 0)
5    map := map[rune]rune{'(': ')', '{': '}', '[': ']'}
6
7    for _, char := range s {
8        if val, exists := map[char]; exists {
9            stack = append(stack, val)
10        } else if len(stack) == 0 || char != stack[len(stack)-1] {
11            return false
12        } else {
13            stack = stack[:len(stack)-1]
14        }
15    }
16    return len(stack) == 0
17}

In all of these solutions, the algorithm remains pretty much the same. We iterate through the string, pushing the corresponding closing bracket onto the stack whenever we encounter an opening bracket. If we encounter a closing bracket and the stack is empty or the top of the stack isn't equal to the closing bracket, we know the parentheses are not balanced and return false. If the string has been fully processed and the stack is empty, we return true, as that indicates a balanced string.

This is a universal solution that can be implemented in any programming language that has support for the stack data structure and it demonstrates one of the many practical uses of stack as a data structure.