Valid Parentheses: Ensuring Correct Closure and Nesting

The "Valid Parentheses" problem involves determining whether a string made up of parentheses, brackets, and braces is valid in terms of closure and nesting.

Problem Statement

Given a string containing characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. The brackets must close in the correct order, meaning "()" and "()[]{}" are valid, but "(]" and "([)]" are not.

Example

• Input: "()[]{}"
• Output: true
• Input: "(]"
• Output: false

Solution Approach - Stack Utilization (typescript)

function isValid(s: string): boolean {
  let stack: string[] = [];
  const mappings = new Map([
    [")", "("],
    ["}", "{"],
    ["]", "["],
  ]);

  for (let char of s) {
    if (mappings.has(char)) {
      const topElement = stack.length === 0 ? "#" : stack.pop();
      if (topElement !== mappings.get(char)) {
        return false;
      }
    } else {
      stack.push(char);
    }
  }

  return stack.length === 0;
}

Breaking Down the Solution

• Using a Stack: A stack is used to keep track of opening brackets.
• Map for Mappings: A map holds the pairs of corresponding opening and closing brackets.
• Validating Closure: For each closing bracket, check if the top of the stack is the corresponding opening bracket. If not, the string is invalid.
• Empty Stack: If the stack is empty at the end, the string is valid.

Conclusion

The Valid Parentheses problem is a classic example of using a stack to ensure proper closure and nesting of brackets in a string. It's a fundamental exercise in balancing and ordering in data structures.