DEV Community

Discussion on: Daily Challenge #101 - Parentheses Generator

Collapse
 
willsmart profile image
willsmart • Edited

This is another case where dynamic programming is useful.
Refactoring the problem as "Give me all the valid (eg. don't end in an open) parenthesis combos of some given string length which, in aggregate, close some given number of parentheses along their length"
Then we get a nice substructure to work with: the result for some given length is just an easy convolution on the result for a smaller length.

Hmm, that came out a bit confusing.
Hopefully the code is easier to follow...

TypeScript:

const memoKey = ({
  aggregateCloseCount,
  length
}: {
  aggregateCloseCount: number;
  length: number;
}): string => `${aggregateCloseCount} ${length}`;

const parenPermutationsMemo: { [key: string]: string[] } = {};

const parenPermutations = ({
  aggregateCloseCount = 0,
  length
}: {
  aggregateCloseCount?: number;
  length: number;
}): string[] => {
  // clip away impossible param settings:
  //   if `aggregateCloseCount<0` any string would need to open more than it closes, which would result in an invalid paren combo
  //   if `aggregateCloseCount>length` any string would need to have more close chars than chars overall
  if (aggregateCloseCount < 0 || aggregateCloseCount > length) return [];

  // early exit for `length==0`
  if (length == 0) return [""];

  const key = memoKey({ aggregateCloseCount, length });
  return (
    parenPermutationsMemo[key] ||
    (parenPermutationsMemo[key] = ["(", ")"].flatMap(prefix =>
      parenPermutations({
        length: length - 1,
        aggregateCloseCount:
          aggregateCloseCount + Number(prefix == "(") - Number(prefix == ")")
      }).map(perm => prefix + perm)
    ))
  );
};

const parenPairPermutations = (pairs: number): string[] =>
  parenPermutations({ length: pairs * 2 });

A couple of runs...

console.log(parenPairPermutations(3));
//> Array(5) ["((()))", "(()())", "(())()", "()(())", "()()()"]

// The main advantage of this approach is better complexity, coping with higher counts
const grindTestPairCount = 14;
console.time(`Time for ${grindTestPairCount} pairs`);
console.log(
  `There are ${
    parenPairPermutations(grindTestPairCount).length
  } permutations for ${grindTestPairCount} pairs of parens`
);
console.timeEnd(`Time for ${grindTestPairCount} pairs`);
//> There are 2674440 permutations for 14 pairs of parens
//> Time for 14 pairs: 6208.31201171875ms
//(old mac pro)