Programming problem: Valid Parentheses

Question

You are given a string s consisting of the following characters: '(', ')', '{', '}', '[' and ']'.

The input string s is valid if and only if:

1. Every open bracket is closed by the same type of close bracket.
2. Open brackets are closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

Return true if s is a valid string, and false otherwise.

Example 1

Input: s = "[]"

Output: true

Example 2

Input: s = "([{}])"

Output: true

Example 3

Input: s = "[(])"

Output: false

Explanation: The brackets are not closed in the correct order.

Constraints

• 1 <= s.length <= 1000

Solution

function isOpenningBracket(char: string): boolean {
  return "({[".includes(char);
}

function isClosingBracket(char: string): boolean {
  return ")}]".includes(char);
}

function isPair(leftChar: string, rightChar: string): boolean {
  const PAIRS: Record<string, string> = {
    "(": ")",
    "{": "}",
    "[": "]",
  };

  return PAIRS[leftChar] === rightChar;
}

function isValid(s: string): boolean {
  // String has an odd number of characters, return false
  if (s.length % 2 !== 0) return false;

  // First character is a closing bracket, return false
  if (!isOpenningBracket(s[0])) return false;

  let i: number = 0;

  while (i < s.length) {
    // Reached the end of the string
    if (!s[i + 1]) return false;

    // Next char is an openning bracket, set index to it and continue
    if (isOpenningBracket(s[i + 1])) {
      i++;
      continue;
    }

    // Mext char is a closing bracket and it's not a pair, return false
    if (isClosingBracket(s[i + 1]) && !isPair(s[i], s[i + 1])) {
      return false;
    }

    // Found a pair, remove brackets from the string and start over
    const before = s.slice(0, i);
    const after = s.slice(i + 2);
    s = `${before}${after}`;
    i = 0;
  }

  return true;
}