Model answer
The task
Convert each lowercase English word into its Morse-code representation, then return the number of distinct representations. Different words may produce the same representation.
Key idea
Use a table mapping each letter to its Morse code. Build each word’s representation by concatenating the codes for its letters, and store those representations in a set to remove duplicates.
Approach
- Define the Morse-code string for each letter from
a through z. - Create an empty set for the representations.
- For each word, translate its letters using the table and join the codes.
- Add the translated word to the set.
- Return the set’s size.
from typing import List
class Solution:
def uniqueMorseRepresentations(self, words: List[str]) -> int:
# Index 0 corresponds to 'a', index 25 to 'z'.
morse = [
".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....",
"..", ".---", "-.-", ".-..", "--", "-.", "---", ".--.",
"--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-",
"-.--", "--..",
]
representations = set()
for word in words:
# Convert each letter to its code, then combine the codes.
encoded = "".join(morse[ord(letter) - ord("a")] for letter in word)
representations.add(encoded)
return len(representations)
Complexity:
- Time: O(S), where S is the total number of letters across all words.
- Space: O(S) in the worst case for the set of stored representations.
Common follow-ups
- What if letters can be uppercase? Normalize each word to lowercase before translating.
- What if the alphabet is larger or mappings change? Use a dictionary from symbols to codes instead of a fixed array.
- Can the set be avoided? In general, distinctness requires tracking seen representations; a set is the direct approach.