May 31st 2023

Balanced parens — Typescript

Problem Description

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order. Every close bracket has a corresponding open bracket of the same type.

Example 1:

Input: s = "()"
Output: true

Example 2:

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

Example 3:

Input: s = "(]"
Output: false

Solution

// Util functions
function expect(description: string, test: boolean) {
    if (test) {
        console.log(`✅ ${description}`)
    } else {
        console.log(`❌ ${description}`)
    }
}

// () [] {}
function isValid(s: string): boolean {
    let brackets: string[] = [];

    for (let char of s.split("")) {
        if (["[", "{", "("].includes(char)) {
            brackets.push(char)
        } else if (["]", "}", ")"].includes(char)) {
            let opener = brackets.pop();
            let closer = char;

            switch (`${opener}${closer}`) {
                case "[]":
                case "{}":
                case "()":
                    break;
                default:
                    return false;
            }
        }
    }

    return brackets.length == 0
};

Discussion

There's a test suite for this project but my blog template function can't handle the complicated parens and blows up (thanks, liquid).

I worked through 3 versions of this as tests got more complicated.

  • Using boolean
  • Using count
  • Using stack