My solution to a leetcode problem

readme.md

Download this gist as a zip, then install and run as follows:

npm install
npx ts-node groupAnagrams.ts

groupAnagrams.ts

// Originally from https://leetcode.com/problems/group-anagrams/

/* Prompt */

// #------------------#
// # Coding question: #
// # Group anagrams   #
// #------------------#
//
// Given an array of strings, group the strings that are anagrams of each other.
// You can return the answer in any order.
//
// An Anagram is a word or phrase formed by rearranging the letters of a
// different word or phrase, using all the original letters exactly
// once.

/* Interviewer notes */

// One approach is to sort each word and then group them by the sorted
// "canonical" word. If the words are small, this will run quickly enough. It
// ought to be possible to write a solution that runs in O(n*k) time, but it's
// tricky to implement an efficient O(k) comparison of the anagrams without
// accidentally doing some sorting somewhere.
//
// Because many solutions involve using maps/hashtables, make sure not to
// accidentally condense duplicates (either duplicate input words, or duplicate
// letters within a word).

/* Sample solution */

/*
 * Sort each word to find those that are anagrams of each other, then group the
 * ones whose sorted representations are the same. This will be O(n * k * lg k)
 * time and O(n*k) space, where n is the number of words and k is the length of
 * the longest word. In practice, hopefully k will be small enough that it's
 * near 1.
 *
 * This function returns a map, which isn't quite the output requested in the
 * problem statement (see below).
 */
function groupAnagramsWithMap(
  words: ReadonlyArray<string>
): ReadonlyMap<string, string[]> {
  const groups = new Map<string, string[]>();

  for (const word of words) {
    const letters = word.split('');
    letters.sort();
    const canonicalWord = letters.join('');

    const group = groups.get(canonicalWord) || [];
    group.push(word);
    groups.set(canonicalWord, group);
  }

  return groups;
}

/**
 * Converts the map returned by the function above into an array of arrays, as
 * requested by the problem.
 */
function convertResultToArray(
  wordMap: ReadonlyMap<string, string[]>
): string[][] {
  const result = [];
  for (const wordSet of wordMap.values()) {
    result.push(wordSet);
  }
  return result;
}

/**
 * Same thing as above but with a plain object instead of a map. To get the array of
 * arrays, we can just call `Object.values` on the result.
 */
function groupAnagramsWithObject(
  words: ReadonlyArray<string>
): Record<string, string[]> {
  const groups: Record<string, string[]> = {};

  for (const word of words) {
    const letters = word.split('');
    letters.sort();
    const canonicalWord = letters.join('');

    const group = groups[canonicalWord] || [];
    group.push(word);
    groups[canonicalWord] = group;
  }

  return groups;
}

/*
 * Test Cases
 */

function doTest(args: {
  name: string;
  input: ReadonlyArray<string>;
  expectedOutput: ReadonlyArray<ReadonlyArray<string>>;
}) {
  const { name, input, expectedOutput } = args;

  const resultMap = groupAnagramsWithMap(input);
  const result = convertResultToArray(resultMap);
  console.log(`\nTest case: ${name}`);
  console.log(input);
  console.log(`Expected:`);
  console.log(expectedOutput);
  console.log(`Actual:`);
  console.log(result);
}

doTest({
  name: 'Conventional example',
  input: ['eat', 'tea', 'tan', 'ate', 'nat', 'bat'],
  expectedOutput: [['bat'], ['nat', 'tan'], ['ate', 'eat', 'tea']],
});
doTest({
  name: 'Duplicate letters',
  input: ['prep', 'perp', 'pep', 'rep', 'per'],
  expectedOutput: [['prep', 'perp'], ['pep'], ['per', 'rep']],
});
doTest({
  name: 'Duplicate words should not be de-duped in the output',
  input: ['car', 'arc', 'arc', 'radio'],
  expectedOutput: [['car', 'arc', 'arc'], ['radio']],
});
doTest({
  name: 'Empty string',
  input: ['', ''],
  expectedOutput: [['', '']],
});
doTest({
  name: 'Single entry',
  input: ['a'],
  expectedOutput: [['a']],
});

package.json

{
  "dependencies": {
    "@types/node": "^14.14.34",
    "ts-node": "^9.1.1",
    "typescript": "^4.2.3"
  }
}

tsconfig.json

{
  "compilerOptions": {
    "target": "ES6"
  }
}