DEV Community

Discussion on: Daily Challenge #101 - Parentheses Generator

Collapse
 
erezwanderman profile image
erezwanderman

Typescript!

First, solving it with numbers. Each solution string is represented by an array of numbers with number incrementing for "(" and decrementing for ")".
For example, "(())()" is [1, 2, 1, 0, 1, 0]

The recursive helper function "solveWithNumbers" receives the beginning of a solution and returns an array with all complete solutions starting with these numbers.

The function "paren" runs "solveWithNumbers" and then converts the solution to the required format

const solveWithNumbers = (startingNumbers: number[], requiredLength: number): number[][] => {
  if (requiredLength === 0) return [ startingNumbers ];
  if (startingNumbers.length === 0) return solveWithNumbers([...startingNumbers, 1], requiredLength - 1);
  const lastNumber = startingNumbers[startingNumbers.length - 1];
  if (lastNumber === 0) return solveWithNumbers([...startingNumbers, 1], requiredLength - 1);
  if (lastNumber === requiredLength) return solveWithNumbers([...startingNumbers, lastNumber - 1], requiredLength - 1);
  return [...solveWithNumbers([...startingNumbers, lastNumber - 1], requiredLength - 1), ...solveWithNumbers([...startingNumbers, lastNumber + 1], requiredLength - 1)];
}

const paren = (n) => solveWithNumbers([], n * 2).map(
  s => s.map(
    (x, i, a) => (i && (a[i - 1] < x ? '(' : ')')) || '('
  ).join('')
);


for (let i = 0; i < 10; i++) {
  console.log(i, paren(i));
}

[stackblitz.com/edit/typescript-n51vvd]