Valid Parentheses LeetCode Solution in JavaScript and TypeScript

The Valid Parentheses problem is a fundamental algorithmic challenge that tests your understanding of stack data structures and string manipulation. This comprehensive guide will walk you through various approaches to solve this popular LeetCode problem (#20) using TypeScript, while explaining the underlying concepts and optimization techniques.

Problem Statement

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.

Example 1:

1Input: s = "()"
2Output: true

Example 2:

1Input: s = "()[]{}"
2Output: true

Example 3:

1Input: s = "(]"
2Output: false

Understanding the Problem

The Valid Parentheses problem is a classic example of using a stack data structure. The key insights are:

1. When we encounter an opening bracket, we push it onto the stack
2. When we encounter a closing bracket, we check if it matches the most recent opening bracket
3. If there's a mismatch or the stack is empty when we need to pop, the string is invalid
4. After processing all characters, the stack should be empty for a valid string

Let's implement different approaches and discuss their trade-offs.

TypeScript Implementation

1. Basic Stack Solution

1function isValid(s: string): boolean {
2    // Handle empty string
3    if (s.length === 0) return true;
4    if (s.length % 2 !== 0) return false;
5
6    // Create a stack to store opening brackets
7    const stack: string[] = [];
8    
9    // Define bracket pairs
10    const bracketPairs: { [key: string]: string } = {
11        ')': '(',
12        '}': '{',
13        ']': '['
14    };
15
16    // Process each character
17    for (const char of s) {
18        if (!bracketPairs[char]) {
19            // Opening bracket
20            stack.push(char);
21        } else {
22            // Closing bracket
23            if (stack.pop() !== bracketPairs[char]) {
24                return false;
25            }
26        }
27    }
28
29    // Stack should be empty for valid string
30    return stack.length === 0;
31}

2. Optimized Solution with Early Returns

1function isValid(s: string): boolean {
2    // Early validation
3    if (s.length === 0) return true;
4    if (s.length % 2 !== 0) return false;
5    if (s[0] === ')' || s[0] === '}' || s[0] === ']') return false;
6
7    const stack: string[] = [];
8    const openBrackets = new Set(['(', '{', '[']);
9    const bracketMap = new Map([
10        [')', '('],
11        ['}', '{'],
12        [']', '[']
13    ]);
14
15    for (let i = 0; i < s.length; i++) {
16        const char = s[i];
17        
18        if (openBrackets.has(char)) {
19            stack.push(char);
20        } else {
21            const lastOpen = stack.pop();
22            if (lastOpen !== bracketMap.get(char)) {
23                return false;
24            }
25        }
26    }
27
28    return stack.length === 0;
29}

3. Memory-Efficient Solution

1function isValid(s: string): boolean {
2    // Early validation
3    if (s.length === 0) return true;
4    if (s.length % 2 !== 0) return false;
5
6    let stack = '';
7    const pairs = {
8        ')': '(',
9        '}': '{',
10        ']': '['
11    };
12
13    for (let i = 0; i < s.length; i++) {
14        const char = s[i];
15        if (!pairs[char]) {
16            stack += char;
17        } else {
18            if (stack[stack.length - 1] !== pairs[char]) {
19                return false;
20            }
21            stack = stack.slice(0, -1);
22        }
23    }
24
25    return stack.length === 0;
26}
27
28// Example usage
29console.log(isValid("()"));      // true
30console.log(isValid("()[]{}"));  // true
31console.log(isValid("(]"));      // false
32console.log(isValid("([)]"));    // false
33console.log(isValid("{[]}"));    // true

Code Analysis and Complexity

Let's analyze our optimized solution:

Time Complexity

• O(n) - We iterate through the string once
• Each stack operation (push/pop) is O(1)

Space Complexity

• O(n) - In worst case, we might need to store all characters in the stack
• For strings with only opening brackets, we'll use maximum space

Performance Optimization Tips

1. Early Validation

   • Check string length is even
   • Check first character isn't a closing bracket
   • Validate input string contains only valid characters

2. Data Structure Choice

   • Use array for stack operations
   • Use Map/Set for constant-time lookups
   • Consider string-based stack for small inputs

3. Memory Management

   • Clear references when possible
   • Use primitive types where appropriate
   • Consider string-based implementation for memory constraints

Common Edge Cases and Input Validation

1function isValid(s: string): boolean {
2    // Input validation
3    if (typeof s !== 'string') {
4        throw new TypeError('Input must be a string');
5    }
6
7    // Handle empty and odd-length strings
8    if (s.length === 0) return true;
9    if (s.length % 2 !== 0) return false;
10
11    // Validate characters
12    const validChars = new Set(['(', ')', '{', '}', '[', ']']);
13    if (![...s].every(char => validChars.has(char))) {
14        return false;
15    }
16
17    const stack: string[] = [];
18    const pairs = new Map([
19        [')', '('],
20        ['}', '{'],
21        [']', '[']
22    ]);
23
24    for (const char of s) {
25        if (!pairs.has(char)) {
26            stack.push(char);
27        } else if (stack.pop() !== pairs.get(char)) {
28            return false;
29        }
30    }
31
32    return stack.length === 0;
33}

Related Problems

• Generate Parentheses (LeetCode #22)
• Longest Valid Parentheses (LeetCode #32)
• Remove Invalid Parentheses (LeetCode #301)

External Resources

• Original LeetCode Problem
• Stack Data Structure
• Time Complexity Analysis
• JavaScript Array Methods

Interview Tips

When solving this problem in an interview:

1. Start by explaining the stack data structure approach
2. Discuss edge cases and input validation
3. Mention potential optimizations and trade-offs
4. Consider memory efficiency vs. code readability
5. Be prepared to handle follow-up questions about different bracket types

Related Concepts

• Stack Data Structure
• String Manipulation
• Hash Maps and Sets
• Time/Space Complexity Analysis
• Input Validation Techniques

Real-World Applications

The Valid Parentheses problem has several practical applications:

1. Code Editors

   • Syntax validation
   • Bracket matching
   • Auto-completion

2. Compilers

   • Expression parsing
   • Syntax checking
   • Code validation

3. Text Processing

   • Mathematical expression validation
   • XML/HTML tag matching
   • JSON structure validation

Conclusion

The Valid Parentheses problem is an excellent example of how fundamental data structures like stacks can be used to solve seemingly complex problems efficiently. While the solution might appear straightforward, the problem teaches important concepts about data structure selection, edge case handling, and code optimization.

Understanding this problem helps build a strong foundation for more complex string manipulation and parsing challenges. It's a frequent interview question at top tech companies because it tests multiple important concepts: data structure knowledge, edge case handling, and code organization.

Remember to practice with various test cases and edge scenarios to fully understand the implementation nuances. Consider the trade-offs between different approaches and be prepared to discuss optimization strategies in an interview setting.