Problem Description

The "Unique Morse Code Words" problem asks you to determine how many unique Morse code transformations exist among a given list of words.

Specifically, you are given an array words where each element is a string consisting of lowercase English letters. Each letter can be converted to a Morse code string based on the international Morse code table. You must:

• Translate each word in words into its Morse code representation by replacing each letter with its corresponding Morse code symbol and concatenating the results.
• Count how many distinct Morse code representations there are among all the words in the input.

• Each word contains only lowercase English letters.
• There is no restriction on the length of the words or the number of words.
• Each Morse code transformation must be counted only once, even if multiple words translate to the same Morse code string.

Thought Process

To solve this problem, the main challenge is efficiently counting the number of unique Morse code transformations. Let's break down the steps:

• Naive/Brute-force concept: For each word, convert it to Morse code, then check if this Morse code string has already been seen. If not, count it as unique.
• Optimization insight: Since we only care about uniqueness, we can use a data structure that automatically handles duplicates—like a set. This way, as we translate each word, we add its Morse code result to the set, and at the end, the size of the set gives us the answer.
• Data mapping: We'll need a way to map each letter to its Morse code string. Since the English alphabet has 26 letters, we can use an array (where index 0 is 'a', index 1 is 'b', etc.) for fast lookup.

Solution Approach

Let's outline the steps to solve the problem:

1. Prepare the Morse code mapping: Create an array where each entry corresponds to the Morse code for a letter ('a' to 'z'). This allows quick lookup based on the letter's position in the alphabet.
2. Iterate through each word: For every word in the input list:
   • For each character in the word, find its Morse code equivalent and concatenate to form the word's Morse code transformation.
3. Track unique transformations: As each word is translated to Morse code, add the result to a set. The set automatically ensures uniqueness.
4. Return the result: The number of unique Morse code transformations is simply the size of the set after processing all words.

Example Walkthrough

Let's walk through an example with the following input:
words = ["gin", "zen", "gig", "msg"]

Step-by-step:

1. For "gin":
   • 'g' → "--."
   • 'i' → ".."
   • 'n' → "-."
   • Concatenate: "--...-."
2. For "zen":
   • 'z' → "--.."
   • 'e' → "."
   • 'n' → "-."
   • Concatenate: "--...-."
3. For "gig":
   • 'g' → "--."
   • 'i' → ".."
   • 'g' → "--."
   • Concatenate: "--...--."
4. For "msg":
   • 'm' → "--"
   • 's' → "..."
   • 'g' → "--."
   • Concatenate: "--...--."

• "gin" → "--...-."
• "zen" → "--...-."
• "gig" → "--...--."
• "msg" → "--...--."

Time and Space Complexity

Brute-force approach:

• If we used a list to store transformations and checked for duplicates manually, for each word (n words), we'd potentially compare with all previous transformations (O(n^2)), which is inefficient.

• Time Complexity: O(n * k), where n is the number of words and k is the average length of a word. For each word, we process each letter once, and set insertion is O(1) on average.
• Space Complexity: O(n * k) in the worst case, where all words have unique transformations and each transformation is stored in the set.

Code Implementation

class Solution:
    def uniqueMorseRepresentations(self, words):
        morse = [
            ".-","-...","-.-.","-..",".","..-.","--.","....","..",
            ".---","-.-",".-..","--","-.","---",".--.","--.-",".-.",
            "...","-","..-","...-",".--","-..-","-.--","--.."
        ]
        seen = set()
        for word in words:
            code = ''.join(morse[ord(c) - ord('a')] for c in word)
            seen.add(code)
        return len(seen)
      

class Solution {
public:
    int uniqueMorseRepresentations(vector<string>& words) {
        vector<string> morse = {
            ".-","-...","-.-.","-..",".","..-.","--.","....","..",
            ".---","-.-",".-..","--","-.","---",".--.","--.-",".-.",
            "...","-","..-","...-",".--","-..-","-.--","--.."
        };
        unordered_set<string> seen;
        for (const string& word : words) {
            string code;
            for (char c : word) {
                code += morse[c - 'a'];
            }
            seen.insert(code);
        }
        return seen.size();
    }
};
      

class Solution {
    public int uniqueMorseRepresentations(String[] words) {
        String[] morse = {
            ".-","-...","-.-.","-..",".","..-.","--.","....","..",
            ".---","-.-",".-..","--","-.","---",".--.","--.-",".-.",
            "...","-","..-","...-",".--","-..-","-.--","--.."
        };
        Set<String> seen = new HashSet<>();
        for (String word : words) {
            StringBuilder code = new StringBuilder();
            for (char c : word.toCharArray()) {
                code.append(morse[c - 'a']);
            }
            seen.add(code.toString());
        }
        return seen.size();
    }
}
      

var uniqueMorseRepresentations = function(words) {
    const morse = [
        ".-","-...","-.-.","-..",".","..-.","--.","....","..",
        ".---","-.-",".-..","--","-.","---",".--.","--.-",".-.",
        "...","-","..-","...-",".--","-..-","-.--","--.."
    ];
    const seen = new Set();
    for (let word of words) {
        let code = '';
        for (let c of word) {
            code += morse[c.charCodeAt(0) - 'a'.charCodeAt(0)];
        }
        seen.add(code);
    }
    return seen.size;
};
      

Summary

The Unique Morse Code Words problem is a classic example of mapping and deduplication. By translating each word into its Morse code representation and storing these in a set, we efficiently count the number of unique transformations. The solution leverages a simple mapping array for fast lookup and a set for uniqueness, making the approach both elegant and efficient. This method avoids unnecessary comparisons and demonstrates the power of combining data structures for clean solutions.