Leetcode 804. Unique Morse Code Words

I’ve been working hard on algorithms lately, so here let’s solve Leetcode’s medium problem #804. Unique Morse Code Words.

The problem reads…

International Morse Code defines a standard encoding where each letter is mapped to a series of dots and dashes, as follows:

'a' maps to ".-",

'b' maps to "-...",

'c' maps to "-.-.", and so on.

For convenience, the full table for the 26 letters of the English alphabet is given below:

[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]

Given an array of strings words where each word can be written as a concatenation of the Morse code of each letter.

For example, "cab" can be written as "-.-..--...", which is the concatenation of "-.-.", ".-", and "-...". We will call such a concatenation the transformation of a word.

Return the number of different transformations among all words we have.

Example 1:

Input: words = ["gin","zen","gig","msg"]
Output: 2
Explanation: The transformation of each word is:
"gin" -> "--...-."
"zen" -> "--...-."
"gig" -> "--...--."
"msg" -> "--...--."
There are 2 different transformations: "--...-." and "--...--.".

The way I like to approach my algos is first to ensure I know what they’re asking for the return. Here we’re not returning an array of words transformed to morse code. Instead we’re turning each of the words given to us in an array into morse code, concatenating them back together and then returning the number of what they’re calling “transformations” from words spelled with letters to words spelled with morse code. Our example makes the ask even clearer.

“gin” in morse code is --. .. -.
"zen" in morse code is --.. . -.

As you can see when I space the letters out they’re clearly different, but when we concatenate as we are instructed to do, they become identical and therefore count as one transformation.

Now that I understand what they mean by “transformation” I like to check out the constraints, which are pretty straightforward in this problem. Our array will consist of at least one and up to 100 words. Each word will consist of at least one, and up to twelve letters. The words will only be made up of lower case English letters. The constraints are pretty straight forward so let’s jump into the problem solve.

The first thing that comes to mind to decide on how to handle is that we’re looking for unique transformations, so my inclination is to use a Set to ensure that uniqueness.

const uniqueMorseRepresentations = function(words) {
   return new Set()
}

We’ve been given the morse alphabet as an array, but what if we just manually turn that into a hash?

let morseAlpha = { a: ".-", b: "-...", c: "-.-.", d: "-..", e: ".", f: "..-.", g: "--.", h: "....", i: "..", j: ".---", k: "-.-", l: ".-..", m: "--", n: "-.", o: "---", p: ".--.", q: "--.-", r: ".-.", s: "...", t: "-", u: "..-", v: "...-", w: ".--", x: "-..-", y: "-.--", z: "--.."}

Awesome! Now that we basically have a translation key and a plan to make a Set (and return the size of that set), how will we solve the problem?

We need to take the string at each index and then return the morse code equivalent of each letter in each string entry. I decided to use good old .map() (twice!) to work this problem out.

So first I’m going to map my word array and split each word.

words.map(word => word.split(''))

Which results in…

Input: ["gin", "zen", "gig", "msg"]
[
   ['g', 'i', 'n'],
   ['z', 'e', 'n'],
   ['g', 'i', 'g'],
   ['m', 's', 'g']
]

Gin? Zen? Yes!

Now that each of our words is an array of letters, we can map this array and replace our letters with their morse code equivalent.

words.map(word => word.split('').map(letter => morseAlpha[letter]))

This second map results in…

[
  [ '--.', '..', '-.' ],
  [ '--..', '.', '-.' ],
  [ '--.', '..', '--.' ],
  [ '--', '...', '--.' ]
]   

Right now this shows that we have 4 unique transformations, but that’s just because we haven’t joined them back together yet, so we should probably just use good old .join(), yeah? Yeah.

words.map(word => word.split('').map(letter => morseAlpha[letter]).join(''))

This gives us this…

[ '--...-.', '--...-.', '--...--.', '--...--.' ]

And when we put this work into a new Set we get

[ '--...-.', '--...--.' ]

Which is great, except we only want the number of transformations instead of the actual transformations, so if we just add on a quick .size, and return the whole thing it looks like this…

const uniqueMorseRepresentations = function(words) {
    
    let morseAlpha = { a: ".-", b: "-...", c: "-.-.", d: "-..", e: ".", f: "..-.", g: "--.", h: "....", i: "..", j: ".---", k: "-.-", l: ".-..", m: "--", n: "-.", o: "---", p: ".--.", q: "--.-", r: ".-.", s: "...", t: "-", u: "..-", v: "...-", w: ".--", x: "-..-", y: "-.--", z: "--.."}
                
     return new Set(words.map(word => word.split('').map(letter => morseAlpha[letter]).join(''))).size
};

and returns

2

And that’s that!