Unique Morse Code Words Interview Question for Google

International Morse Code defines a standard encoding where each letter is mapped to a series of dots and dashes. Given an array of strings words where each word can be written as a concatenation of the Morse code of each letter, return the number of different transformations among all words. For example:

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

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

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

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 "--...--.".

Example 2:

Input: words = ["a"]
Output: 1

How would you implement a function to solve this problem, and what is the time and space complexity of your solution?

Naive Solution

The most straightforward approach is to iterate through the words array, transform each word into its Morse code representation, and then store the transformations in a set. The size of the set will give us the number of distinct transformations.

Code

def uniqueMorseRepresentations(words):
    morse_code = [".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.."]
    transformations = set()
    for word in words:
        transformation = ""
        for char in word:
            transformation += morse_code[ord(char) - ord('a')]
        transformations.add(transformation)
    return len(transformations)

Time and Space Complexity

Time Complexity: O(N * M), where N is the number of words and M is the average length of a word. We iterate through each word and for each character, we perform a constant-time lookup.
Space Complexity: O(N), where N is the number of words in the worst case where all words have different morse code transformations. This is for storing the transformations in the set.

Optimal Solution

The "optimal" solution does not drastically differ from the naive one. The core logic remains the same: transform each word and store the unique results. However, minor optimizations might involve using more efficient data structures or pre-calculating the Morse code array.

In practice, the naive solution is performant enough given the problem constraints, so focusing on code clarity and readability is often preferred.

Edge Cases

Empty input array: Should return 0 (although the problem states 1 <= words.length <= 100 so this is not an issue)
Words with non-lowercase English letters: The code assumes only lowercase english letters, so it should return the wrong results.

Code (Same as Naive Solution)

def uniqueMorseRepresentations(words):
    morse_code = [".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.."]
    transformations = set()
    for word in words:
        transformation = ""
        for char in word:
            transformation += morse_code[ord(char) - ord('a')]
        transformations.add(transformation)
    return len(transformations)