LeetCode Meditations: Valid Parentheses
Tags: computerscience, algorithms, typescript, javascript
Published: 2024-03-19 09:47:58

The description for [this problem](https://leetcode.com/problems/valid-parentheses) says:

> Given a string `s` containing just the characters `'('`, `')'`, `'{'`, `'}'`, `'['` and `']'`, determine if the input string is valid.
>
> An input string is valid if:
> 
> 1. Open brackets must be closed by the same type of brackets.
> 2. Open brackets must be closed in the correct order.
> 3. Every close bracket has a corresponding open bracket of the same type.

For example: 

```ts
isValid('()');
// -> true


isValid('()[]{}');
// -> true


isValid('(]');
// -> false
```

---

The first idea that comes to mind is, perhaps, adding each parenthesis in the string to a stack, and once we come to one of the closing parentheses, we can check if the previous parenthesis is its opening pair. If so, we can pop them both off the stack. If we are left with an empty stack at the end, that means all the parentheses match, so we can return `true`; otherwise, we'll return `false`.

For example, if our string is `([{}])` (which is valid), it will look like this:


![Stack for checking valid parentheses](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/eczwzzumgttz5x11idw2.gif)

My initial solution in TypeScript looked like this:

```ts
function isValid(s: string): boolean {
  let stack = [];
  const opening = ['(', '{', '['];
  const closing = [')', '}', ']'];
  for (const c of s) {
    stack.push(c);
    if (closing.includes(c)) {
      let prevItem = stack[stack.length - 2];
      if (opening.includes(prevItem) && 
          opening.indexOf(prevItem) === closing.indexOf(c)) {
            stack.pop();
            stack.pop();
      }
    }
  }

  if (!stack.length) {
    return true;
  }

  return false;
};
```

However, there is a slightly better way, where we can use a hash table for parentheses, mapping the closing ones to their opening pairs. We also don't have to push every character onto the stack, and can return immediately when the parentheses don't match:

```ts
function isValid(s: string): boolean {
  let stack = [];
  const parentheses = {
    ')': '(',
    ']': '[',
    '}': '{'
  }
  for (const c of s) {
    // If it's a closing parenthesis
    if (c in parentheses) { 
      // If the stack is not empty and the previous item on the stack is its opening pair
      if (stack.length && stack[stack.length - 1] === parentheses[c]) {
        stack.pop();
      } else {
        return false;
      }
    } else {
      stack.push(c);
    }
  }

  if (!stack.length) {
    return true;
  }

  return false;
};
```

Here, as we iterate through the characters of `s`, if it's an opening parenthesis, we'll just push it to our stack. When we come to a closing parenthesis, if our stack is not empty and the last item we added to our stack matches the opening pair of the closing one we're looking at, we can just pop it off the stack. Otherwise, it's not a matching pair, so we can return `false` immediately. 

At the end, if our stack is empty, we can return `true`, otherwise we'll return `false`.

#### Time and space complexity

The time complexity for this solution is {% katex inline %} O(n) {% endkatex %} because in the worst case where each character in the input string is an opening parenthesis, we'll loop through the entire string, so the runtime growth is proportionate to its length.
The space complexity is {% katex inline %} O(n) {% endkatex %} because of our stack, which, in the worst case, will have all the characters in the input string.

---

Next up, we'll start a new chapter on [Binary Search](https://en.wikipedia.org/wiki/Binary_search_algorithm). Until then, happy coding.