[Leetcode] Valid Parentheses

20. Valid Parentheses

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

An input string is valid if:

Open brackets must be closed by the same type of brackets.

Open brackets must be closed in the correct order.

Every close bracket has a corresponding open bracket of the same type.

Example 1:

Input: s = "()"

Output: true

Example 2:

Input: s = "()[]{}"

Output: true

Example 3:

Input: s = "(]"

Output: false

Example 4:

Input: s = "([])"

Output: true

Constraints:

1 <= s.length <= 10``4

s consists of parentheses only '()[]{}'.

how to approach?

function isValid(s: string): boolean {
    let arr = []
    for (let char of s) {
        if (char === '(') arr.push(char)
        if (char === ')') {
            if (arr[arr.length - 1] === '(') {
                arr.pop()
            }
            else return false;
        }

        if (char === '{') arr.push(char)
        if (char === '}') {
            if (arr[arr.length - 1] === '{') {
                arr.pop()
            }
            else return false;
        }

        if (char === '[') arr.push(char)
        if (char === ']') {
            if (arr[arr.length - 1] === '[') {
                arr.pop()
            }
            else return false;
        }
    }

    return arr.length === 0
};

1. create an array to save the parentheses from s string.
2. let's think of this array as stack, so when opening bracket is in s string then put it on the top and if the next bracket is opening bracket then put it on the top so one by one it will be stacked if it's opening brackets.
3. that will be arr.push(char)
4. if char in s is closing bracket/parenthesis then check the last element in stack(what is the top element in the stack?) if it is the opening bracket/parenthesis then check the type of it, if it's [ { (, and then if it's right type then pop it out from the stack.
5. that will be arr.pop()
6. if it's not the right type of bracket/parenthesis of closing bracket/parenthesis then in else block, return false.
7. at the end, it will check the length of the array and array is empty then return true, if it's not(the stack has the element in it), then return the false since the array is not empty.

summary

this leetcode problem is solved by typescript

First create array and check the each parenthesis/bracket in the s string and check the type of it, if it's opening then put it on the top of the stack(arrray).

if it's closing type's bracket/parenthesis, check the top element in the stack and check the type of it, if it's right type then remove the top element.

if it's not right type for the closing bracket then return the false.

after the for loop check if the array is empty.

2025/07/22 NEW solution Stack and Pair

function isValid(s: string): boolean {
    const pairs = {
        '}': '{',
        ']': '[',
        ')': '('
    };
    
    const stack: string[] = [];
    const openBrackets = Object.values(pairs);
    const closeBrackets = Object.keys(pairs);

    for (const char of s) {
        if (openBrackets.includes(char)) {
            stack.push(char);
        } else if (closeBrackets.includes(char)) {
            if (pairs[char] === stack[stack.length - 1]) {
                stack.pop();
            } else {
                return false; 
            }
        }
    }

    return stack.length === 0;
}

1. create pairs using closing bracket as key and opening bracket as value.
2. create stack to store opening brackets.
3. create 2 arrays store opening brackets & closing brackets.
4. create for loop to iterate over s string characters.
5. when the char is opening bracket, then push it to the stack.
6. when the char is closing bracket, check the top element in the stack.
7. check if the pair's value equal to the top element in the stack.
8. if it equals then pop the top element in the stack since it matches to close the bracket.
9. if it's not, then it means the brackets are not the match so return false.
10. after the iteration over the s string, return the stack.length equals to 0 to check the stack is empty.