Unique Morse Code Words Python Solution

LeetCode 804, Easy. Topics: Array, Hash Table, String. View on LeetCode. Generate this problem as a practice environment: tested reference solution, 24 parametrized pytest cases, and a playground notebook:

lcpy gen -n 804   # by problem number
lcpy gen -s unique_morse_code_words   # by problem name

Problem

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.

Examples

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

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

Constraints

1 <= words.length <= 100
1 <= words[i].length <= 12
words[i] consists of lowercase English letters.

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

from typing import ClassVar


class Solution:
    morse: ClassVar[list[str]] = [
        ".-",
        "-...",
        "-.-.",
        "-..",
        ".",
        "..-.",
        "--.",
        "....",
        "..",
        ".---",
        "-.-",
        ".-..",
        "--",
        "-.",
        "---",
        ".--.",
        "--.-",
        ".-.",
        "...",
        "-",
        "..-",
        "...-",
        ".--",
        "-..-",
        "-.--",
        "--..",
    ]

    # Time: O(S) where S is the total number of characters in all words
    # Space: O(S) for the set of transformations
    def unique_morse_representations(self, words: list[str]) -> int:
        def transform(word: str) -> str:
            return "".join(self.morse[ord(c) - ord("a")] for c in word)

        return len({transform(w) for w in words})

Complexity

Time	Space
O(S) where S is the total number of characters in all words	O(S) for the set of transformations

Welcome

Getting Started

Practice

CLI

Catalog

Contributing

Troubleshooting

Unique Morse Code Words Python Solution

Problem

Examples

Constraints

Solution

Complexity

Tags

​Problem

​Examples

​Constraints

​Solution

​Complexity

​Tags

Problem

Examples

Constraints

Solution

Complexity

Tags