leetcode

Valid Parentheses solution using TypeScript

Below is my TypeScript solution to the LeetCode "Valid Parentheses" question.

Time Complexity: Because each character in the string will be visited one time, the time complexity is O(n), where n represents the length of the string.

Space Complexity: This approach will place n elements in the stack in the worst case, making the space complexity O(n).

/**
 * Given a string containing just the characters 
 * '(', ')', '{', '}', '[' and ']', determine if the 
 * input string is valid.
 *
 *   Time Complexity: O(n)
 *   Space Complexity: O(n)
 *
 *   Input:  "{[]}"
 *   Output: true
 */
function isValid(s: string): boolean {
    const stack = [];
    const map = new Map([
        ['}', '{'],
        [']', '['],
        [')', '(']
    ])
    const openingBraces = Array.from(map.values());
    let mismatchedBrace = false;
    
    for (let i = 0; i < s.length; i++) {
        if (openingBraces.includes(s[i])) {
            stack.push(s[i]);
        } else {
            const openingBrace = stack.pop();
            const expectedBrace = map.get(s[i]);
            if (openingBrace !== expectedBrace) {
                mismatchedBrace = true;
                break;
            }
        }
    }
    
    return !mismatchedBrace && !stack.length;
}

more LeetCode posts