Question

LeetCode Link | 20. Valid Parentheses | Easy

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.
  3. Every close bracket has a corresponding open bracket of the same type.

Constrains

  • 1 <= s.length <= 10^4
  • s consists of parentheses only '()[]{}'.

Examples

Example 1

Input: s = “()”
Output: true

Example 2

Input: s = “()[]{}”
Output: true

Example 3

Input: s = “(]”
Output: false

Solution Approach

Method: Stack

Constrains

  • None

This method does not have any limitations.

Concept Explanation

Due to the special characteristics of stack structures, they are very well-suited for symmetry matching problems.

First, it’s important to understand the different scenarios in which parentheses in a string may not match.

It is recommended to analyze the different types of mismatches before writing code. If these scenarios are not well understood beforehand, the resulting code may have many issues.

Let’s analyze the three types of mismatches:

  1. Scenario 1: There are extra left-facing parentheses in the string, resulting in a mismatch.

Parentheses mismatch 1

  1. Scenario 2: There are no extra parentheses, but the types of parentheses do not match. ![image/image-20240510184737733.png)

  2. Scenario 3: There are extra right-facing parentheses in the string, resulting in a mismatch.

Parentheses mismatch 3

As long as our code covers these three types of mismatches, it will be robust. This highlights the importance of thoroughly analyzing the problem before coding.

  1. Scenario 1: After traversing the entire string, if the stack is not empty, it means there are unmatched left parentheses, so return false.
  2. Scenario 2: During the traversal and matching process, if the stack does not have the character to be matched, return false.
  3. Scenario 3: During the traversal and matching process, if the stack is already empty and there are no characters left to match, it means a right parenthesis has not found its corresponding left parenthesis, so return false.

When are all left and right parentheses matched? It’s when, after traversing the entire string, the stack is empty, indicating that all parentheses are matched.

Code

  • Time complexity: O(n)
  • Space complexity: O(n)

TypeScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
function isValid(s: string): boolean {
    let stack: string[] = [];
    type BracketMap = {
        [bracket: string]: string;
    }
    const bracketMap: BracketMap = {
        '(': ')',
        '{': '}',
        '[': ']'
    }

    for (let i of s) {
        // Store left wing bracket into stack
        if (bracketMap.hasOwnProperty(i)) {
            stack.push(bracketMap[i]);
        } 
        // Take out the recent left wing bracket 
        // and compare with the right wing bracket.
        // If not in pair, return false
        else if (i !== stack.pop()) {
            return false;
        }
    }
    
    // If stack not empty means not every close bracket
    // has a corresponding open bracket of the same type.
    return stack.length === 0;
};

Conclusion

Parentheses matching is a classic problem solved using stacks.

The problem is akin to ensuring the order of parentheses in our code is correct: a left parenthesis must have a corresponding right parenthesis in the appropriate position.

If you recall compiler theory, during lexical analysis, compilers handle parentheses, braces, and similar symbols using stack data structures.

Another example is the Linux cd command, which we are quite familiar with:

1
cd a/b/c/../../

This command ultimately navigates to the a directory. How does the system know it has navigated to the a directory? This is an application of stacks (this could actually be a relevant interview question).

Thus, stacks are widely used in the field of computer science.