Validating Parentheses Input Using TypeScript

The Valid Parentheses Problem is a common interview‑type problem but isn't just academic; it also arises fairly frequently in real‑world development scenarios (although not always specifically in coupling parenthesis types), particularly when it comes to lower‑level interpreters or linting tools.

By ensuring that all opened brackets, braces, and parentheses are properly closed in the correct order, you add another layer of robustness to your code.

Understanding the Problem

The task itself is straightforward: Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

• Open brackets are closed by the same type of brackets. And...
• Open brackets are closed in the correct order.

For example, {}, (), or [] are valid whilst (], [), or {[} would not be.

There is an additional layer of complication to this task in that nesting of parenthesis types should also be handled. It is valid to have one type nested inside another, as long as they open and close in the correct consecutive order.

Some Examples

Input: s = "()"
Output: true

Input: s = "(]"
Output: false

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

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

How We Can Solve It

The most straightforward way to tackle this problem is to use a stack data structure. In this context, a stack is a Last‑In, First‑Out (LIFO) data structure where the last element added is the first one to be removed. You could visualise it as being akin to a stack of books; you can only add or remove a book from the top of the stack.

For matching opening and closing brackets, this data structure is a really natural fit. When you encounter an opening bracket, you 'push' it onto the stack, and when you encounter a closing bracket, you 'pop' the last element from the stack to see if they match. By using a stack, we can easily keep track of the brackets and validate them simply and efficiently.

In Code

Here's how you could implement this solution method using TypeScript:

const isValid = (s: string): boolean => {  const stack: string[] = [];  const map: { [key: string]: string } = {    ')': '(',    '}': '{',    ']': '[',  };  for (const char of s) {    if (['(', '{', '['].includes(char)) {      stack.push(char);    } else {      const topElement = stack.pop();      if (map[char] !== topElement) {        return false;      }    }  }  return stack.length === 0;};

How the Code Works

1. We initialise an empty stack and a mapping of closing and opening brackets.
2. We then iterate through the provided string.
3. When an opening bracket is encountered, it is pushed onto the stack.
4. When a closing bracket is encountered, we check if its corresponding opening bracket is at the top of the stack.
5. At the end, if the stack is empty, the string is valid.

Alternative Solution Methods

Apart from using a stack, there are a few other methodologies to solve the Valid Parentheses problem. Although these might not be as efficient or straightforward, they offer different perspectives on solving the problem. Here are some alternative methods:

1. Recursion

A recursive approach can be used where we replace every balanced set of parentheses in the string with an empty string until no more balanced sets can be found. If the string is empty at the end, it's valid.

2. Regular Expression

You could use a regular expression to match pairs of parentheses and remove them iteratively until the string is empty or no more matches can be found.

3. Counter Method

For every type of bracket, you could maintain a separate counter. Increment the counter when an opening bracket is encountered and decrement when a closing one is found. This approach can quickly get complex, and you'd still need to ensure that the brackets close in the correct order, which makes this method tricky.

4. Character Array and Two‑Pointer Technique

I love a two‑pointer solution and have talked about this method a lot previously when tackling similar LeetCode‑type problems. In this instance, we could convert the string to an array of characters and then use two pointers to match each parenthesis. This approach would also involve a lot of index‑tracking and array manipulation, so it isn't totally straightforward here.

5. Balanced Factor and Early Termination

Here you maintain a balance factor for each type of bracket, incrementing when an opening bracket is seen and decrementing for a closing bracket. If ever the balance factor goes negative, you can terminate early, knowing the string is not valid.

Although these methods are not as efficient or straightforward as the stack method, they do offer alternatives that might better suit specific project needs.

Conclusion

Understanding and solving the Valid Parentheses problem is not only crucial for acing coding interviews but also useful in writing cleaner, error‑free code. There are any number of different ways to approach a solution (as is always the case in software development), but at least having read this article, you go away with what I think is the cleanest option, along with a few alternatives to impress your interviewer with!