2b.md

Day 2b: Similar Words - Code

Given an array of ids, find the first two ids that differ by exactly one character at the same position in both strings.

Example:

abcde
fghij
klmno
pqrst
fguij
axcye
wvxyz

The IDs abcde and axcye are close, but they differ by two characters (the second and fourth). However, the IDs fghij and fguij differ by exactly one character, the third (h and u). Those must be the correct boxes.

What letters are common between the two correct box IDs? (In the example above, this is found by removing the differing character from either ID, producing fgij.)

Solution

Convert each word to its generic form. I.e., for the word abcde, create [*bcde, a*cde, ab*de, abc*e, abcd*], and store that in a map. Scan each word one at a time, creating a generic form for every letter in that word. Keep a count in the dictionary. Once the count becomes greater than 1, return the generic form without the *.

const getNthGenericForm = (id: string, n: number) =>
    id.substring(0, n) + '*' + id.substring(n + 1);

export const corpusToGeneric = (ids: string[]) => {
    const map = new Map<string, number>();

    for (let i = 0; i < ids.length; i++)
        for (let j = 0; j < ids[i].length; j++) {
            const generic = getNthGenericForm(ids[i], j);
            map.set(generic, (map.get(generic) ?? 0) + 1);
            if (map.get(generic)! > 1)
                return generic.replace(/\*/, '');
        }
    return map;
};

For the example above, this produces:

Map {
  '*bcde' => 1,
  'a*cde' => 1,
  'ab*de' => 1,
  'abc*e' => 1,
  'abcd*' => 1,
  '*ghij' => 1,
  'f*hij' => 1,
  'fg*ij' => 2,
  'fgh*j' => 1,
  'fghi*' => 1,
  '*lmno' => 1,
  'k*mno' => 1,
  'kl*no' => 1,
  'klm*o' => 1,
  'klmn*' => 1,
  '*qrst' => 1,
  'p*rst' => 1,
  'pq*st' => 1,
  'pqr*t' => 1,
  'pqrs*' => 1,
  '*guij' => 1,
  'f*uij' => 1,
  'fgu*j' => 1,
  'fgui*' => 1,
  '*xcye' => 1,
  'a*cye' => 1,
  'ax*ye' => 1,
  'axc*e' => 1,
  'axcy*' => 1,
  '*vxyz' => 1,
  'w*xyz' => 1,
  'wv*yz' => 1,
  'wvx*z' => 1,
  'wvxy*' => 1
}