🚀 DSA Problem Solving — Day 2

Q1 🧮 Valid Parentheses

🔖 Difficulty: Easy

🔗 Source: LeetCode #20

📘 Topic Tags: String, Stack, Loop

---

🧠 Problem Description

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

A string is considered valid if:

• Open brackets are closed by the same type of brackets.
• Open brackets are closed in the correct order.
• Every closing bracket has a corresponding open bracket of the same type.

---

💡 Constraints

• 1 <= s.length <= 10⁴
• s consists only of the characters: '()[]{}'

---

📥 Input

• A single string s containing only parentheses.

📤 Output

• Return true if the string is valid, otherwise return false.

---

⚙️ Approach (Step-by-Step)

1. Create a mapping object from opening to closing brackets:

   const map = {
     '(': ')',
     '[': ']',
     '{': '}'
   };

1. Use a stack to keep track of expected closing brackets.

2. Iterate through each character in the input string:

• If the character is an opening bracket, push its corresponding closing bracket onto the stack.

• If the character is a closing bracket:

  • Check if it matches the top element of the stack.
  • If it doesn't match or the stack is empty, return false.
  • After the loop, if the stack is empty, return true. Otherwise, return false.

Example

Input: s = "()"
Output: true

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

Input: s = "(]"
Output: false

Input: s = "([)]"
Output: false

Input: s = "{[]}"
Output: true

🧑‍💻 JavaScript Code:

let SymbolsObj = {
    '(': ')',
    '{': '}',
    '[': ']'
};

var isValid = function(s) {
    let stack = [];

    for (let i = 0; i < s.length; i++) {
        let char = s[i];

        if (SymbolsObj[char]) {
            // Opening symbol: push expected closing symbol
            stack.push(SymbolsObj[char]);
        } else {
            // Closing symbol: should match the top of stack
            if (stack.length === 0 || stack.pop() !== char) {
                return false;
            }
        }
    }

    // Stack should be empty if all matched
    return stack.length === 0;
};