🚀 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; };