LeetCode 804: Unique Morse Code Words

Problem Restatement

We are given an array of lowercase English words.

Each letter can be converted into Morse code. A word is transformed by replacing every letter with its Morse code and concatenating the results into one string.

For example, the word "cab" becomes:

"-.-." + ".-" + "-..." = "-.-..--..."

We need to return how many different transformed strings appear among all words. The task is to count unique transformations, not unique original words. The official problem defines the transformation this way and asks for the number of different transformations among all words.

Input and Output

Examples

Example:

words = ["gin", "zen", "gig", "msg"]

The transformations are:

There are only two different transformations:

"--...-.."
"--...--."

So the answer is:

2

Another example:

words = ["a"]

The word "a" transforms to:

".-"

There is one unique transformation, so the answer is:

1

First Thought: Direct Conversion

The problem already gives us a fixed mapping from letters to Morse code.

So the direct approach is:

1. Convert each word into Morse code.
2. Store the converted string.
3. Count how many different converted strings we have.

This is exactly what a set is for.

A set keeps only unique values. If two words produce the same Morse transformation, the set stores that transformation once.

Key Insight

The original word does not matter after conversion.

For example:

"gin" -> "--...-.."
"zen" -> "--...-.."

These are different words, but they produce the same transformation.

Since we only need the number of different transformations, we can insert every transformed word into a set and return the set size.

Algorithm

Create the Morse code table:

codes = [
    ".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..",
    ".---", "-.-", ".-..", "--", "-.", "---", ".--.", "--.-",
    ".-.", "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.."
]

The index of each code matches the letter position:

For each word:

1. Start with an empty list of Morse pieces.
2. For each character ch, compute:

ord(ch) - ord("a")

3. Use that index to get the Morse code.
4. Join the pieces into one string.
5. Add the string to a set.

Return the size of the set.

Correctness

Each character in every input word is a lowercase English letter, so it has exactly one Morse code in the table.

For a word, the algorithm processes its letters from left to right and appends the Morse code of each letter. Therefore, the produced string is exactly the transformation defined by the problem.

The algorithm inserts every transformation into a set. A set stores one copy of each distinct value, so duplicate transformations are counted once.

After all words are processed, the set contains exactly all different Morse transformations from the input. Therefore, returning the set size gives the required answer.

Complexity

Let L be the total number of characters across all words.

The Morse table has 26 entries, so it uses constant extra space.

Implementation

class Solution:
    def uniqueMorseRepresentations(self, words: list[str]) -> int:
        codes = [
            ".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..",
            ".---", "-.-", ".-..", "--", "-.", "---", ".--.", "--.-",
            ".-.", "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.."
        ]

        transformations = set()

        for word in words:
            morse = []

            for ch in word:
                index = ord(ch) - ord("a")
                morse.append(codes[index])

            transformations.add("".join(morse))

        return len(transformations)

Code Explanation

The codes array stores the Morse code for each lowercase English letter:

codes[0]   # Morse code for 'a'
codes[1]   # Morse code for 'b'
codes[25]  # Morse code for 'z'

For each word, we build its transformation:

morse = []

For each character, we convert it to an index:

index = ord(ch) - ord("a")

For example:

ord("a") - ord("a") == 0
ord("b") - ord("a") == 1
ord("z") - ord("a") == 25

Then we append the corresponding Morse code:

morse.append(codes[index])

After processing the whole word, we join all pieces:

"".join(morse)

That complete transformation is inserted into the set:

transformations.add("".join(morse))

Finally, the number of unique transformations is:

len(transformations)

Testing

def run_tests():
    s = Solution()

    assert s.uniqueMorseRepresentations(["gin", "zen", "gig", "msg"]) == 2
    assert s.uniqueMorseRepresentations(["a"]) == 1
    assert s.uniqueMorseRepresentations(["a", "a"]) == 1
    assert s.uniqueMorseRepresentations(["a", "b", "c"]) == 3
    assert s.uniqueMorseRepresentations(["no", "on"]) == 2

    print("all tests passed")

run_tests()