LeetCode Meditations: Valid Parentheses

The description for this problem 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:

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:

My initial solution in TypeScript looked like this:

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:

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 $O(n)$ 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 $O(n)$ 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. Until then, happy coding.