Advent of PBT 2021 - Day 5

/**
 * You're given a message where spaces have been removed.
 * Your aim is to find back the original message given a dictionary
 * containing all the words. As many messages could be encoded the
 * same way, you may have to return two or more messages. No specific
 * ordering is expected when multiple solutions are available but all
 * must be returned.
 *
 * @param spacelessMessage - Message without any spaces
 * @param words - List of accepted words (no repeat and at least one
 * character long)
 *
 * @returns
 * All the possible messages made only with the received words that
 * could have led to this spacelessMessage.
 */
declare function respace(spacelessMessage: string, words: string[]): string[];

it("should be able to detect one match when there is only one", () => {
  const out = respace("helloworld", ["hello", "world"]);
  expect(out).toEqual(["hello world"]);
});

it("should not detect any match and produce empty arrays when no matchs", () => {
  const out = respace("hellowooorld", ["hello", "world"]);
  expect(out).toEqual([]);
});

it("should be able to detect all the matches when multiple are eligible", () => {
  const out = respace("tititi", ["ti", "titi"]);
  expect(sorted(out)).toEqual(["ti ti ti", "ti titi", "titi ti"]);
});