word-chain-recursion.ts

const startsWith = (letter: string) =>
  (word: string) =>
    word[0] === letter;

const isAny = () =>
  true;

const lastLetterOf = (word: string): string =>
  word[word.length - 1];

const isChainPossible = (
  words: string[],
  isEligable: (word: string) => boolean,
): boolean => {
  if (words.length === 1 && isEligable(words[0])) return true;

  for (const [index, word] of words.entries()) {
    if (!isEligable(word)) continue;

    const isPossible = isChainPossible(
      [...words.slice(0, index), ...words.slice(index + 1)],
      startsWith(lastLetterOf(word)),
    );

    if (isPossible) return true;
  }

  return false;
};

const solution = (words: string[]) =>
  isChainPossible(words, isAny);

words-chain.ts

const couldBeBound = (used: Set<number>, startsWith: string) =>
  (word: string, index: number) =>
    word[0] === startsWith && !used.has(index);

const findIndex = <T>(
  list: T[],
  predicate: (item: T, index: number, list: T[]) => boolean,
  start: number = 0,
) => {
  for (let index = start, end = list.length; index < end; index += 1) {
    if (predicate(list[index], index, list)) return index;
  }
  return -1;
};

const last: {
  <T>(list: T[]): T | undefined;
  (str: string): string | undefined;
} = <T>(listOrString: string | T[]) =>
  listOrString[listOrString.length - 1];

const solution = (words: string[]) => {
  const n = words.length;
  const used = new Set<number>();
  const chain: number[] = [];
  let currentChainIndex = 0;
  let currentWordIndex = -1;

  const getNextIndex = () => {
    if (currentChainIndex === 0) return currentWordIndex + 1;
    const lastWordIndex = chain[currentChainIndex - 1];
    const lastWord = words[lastWordIndex];
    return findIndex(
      words,
      couldBeBound(used, last(lastWord)!),
      currentWordIndex,
    );
  };

  while (currentChainIndex < n) {
    const nextIndex = getNextIndex();

    if (nextIndex >= 0 && nextIndex < n) {
      // Step Forward
      chain.push(nextIndex);
      used.add(nextIndex);
      currentChainIndex += 1;
      currentWordIndex = 0;
    } else {
      // Step Backward
      currentChainIndex -= 1;
      if (currentChainIndex < 0) break; // all options checked
      currentWordIndex = chain.pop()!; // we know it's not empty
      used.delete(currentWordIndex);
      if (currentChainIndex > 0) {
        // do it manually only for the second and other
        currentWordIndex += 1;
      }
    }
  }

  return currentChainIndex === n;
};