804 - Unique Morse Code Words

Difficulty: Easy | Pattern: HashSet + String Mapping | Company tags: Amazon, Google

Problem Statement

International Morse Code defines a standard encoding where each letter is mapped to a series of dots and dashes. Given a list of words, return the number of different transformations among all words.

Morse mappings:

a→".-"  b→"-..."  c→"-.-."  d→"-.."  e→"."  f→"..-."
g→"--."  h→"...."  i→".."  j→".---"  k→"-.-"  l→".-.."
m→"--"  n→"-."  o→"---"  p→".--."  q→"--.-"  r→".-."
s→"..."  t→"-"  u→"..-"  v→"...-"  w→".--"  x→"-..-"
y→"-.--"  z→"--.."

Example:

Input: words = ["gin","zen","gig","msg"]
Output: 2
Explanation:
"gin" → "--...-."
"zen" → "--...-."
"gig" → "--...--."
"msg" → "--...--."

Solution

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

Dry Run

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

word	transformation
gin	--. .. -. → "--...-."
zen	--.. . -. → "--...-."
gig	--. .. --. → "--...--."
msg	-- ... --. → "--...--."

Set: {"--...-.", "--...--."} → size = 2 ✓

Complexity

• Time: O(total characters across all words)
• Space: O(total transformations)