LeetCode: Valid Parentheses

In this article, we'll solve the Valid Parentheses problem from LeetCode. This problem involves determining if a given string of parentheses is valid or not.

Problem Statement

The problem can be described as follows:

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

1. Open brackets are closed by the same type of brackets.
2. Open brackets are closed in the correct order.
3. An empty string is also considered valid.

Write a function isValid that takes a string as input and returns true if the string is valid, and false otherwise.

Approach and Code

We can solve this problem using a stack data structure. We'll iterate through the characters of the input string and use a stack to keep track of the open brackets. Whenever we encounter an open bracket, we push it onto the stack. If we encounter a closing bracket, we pop the top element from the stack and check if it matches the current closing bracket. If they match, we continue; otherwise, the string is not valid.

Here's the TypeScript code for the approach:

function isValid(s: string): boolean {
  const stack: string[] = []
  const pairs: { [key: string]: string } = {
    '(': ')',
    '{': '}',
    '[': ']',
  }

  for (let char of s) {
    if (char in pairs) {
      stack.push(char)
    } else {
      const top = stack.pop()
      if (top === undefined || pairs[top] !== char) {
        return false
      }
    }
  }

  return stack.length === 0
}

Example

Let's take an example to understand how the function works. Consider the following input string:

const input = '()[]{}'
const result = isValid(input)
console.log(result) // Output: true

Conclusion

The "Valid Parentheses" problem can be efficiently solved using a stack to keep track of open brackets. The provided TypeScript solution demonstrates how to implement this approach.

For further practice and exploration, you can visit the LeetCode problem page and try out different test cases.

Resources

Here are some top resources to learn more about algorithms, data structures, and problem-solving techniques:

1. Cracking the Coding Interview: 189 Programming Questions and Solutions
2. System Design Interview – An insider's guide Volume 1
3. System Design Interview – An insider's guide Volume 2
4. Daily Coding Problem
5. Designing Data-Intensive Applications: The Big Ideas Behind Reliable, Scalable, and Maintainable Systems
6. LeetCode - The official LeetCode platform for practicing coding problems.
7. GeeksforGeeks - A website with a wide range of computer science topics and coding challenges.
8. Cracking the Coding Interview by Gayle Laakmann McDowell - A comprehensive book on coding interviews and algorithms.