Leetcode 804. Unique Morse Code Words

Problem

You are given an array of strings where each string contains only lowercase English letters. Your task is to transform each word into its Morse code representation and determine how many unique Morse code strings result from these transformations.

In Morse code, each letter of the alphabet is represented by a unique sequence of dots and dashes. The mapping for the 26 lowercase English letters is as follows:

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

To transform a word, concatenate the Morse code representation of each letter in the word. For example, the word "cat" would become "-.-." + ".-" + "-" = "-.-..-".

Return the count of distinct Morse code transformations that appear in the input list.

Requirements

1. Transform each word into its Morse code representation by concatenating the codes of its letters
2. Count and return the number of unique Morse code strings generated
3. Handle words of varying lengths from 1 to 12 characters
4. Process input arrays containing 1 to 100 words

Constraints

• 1 ≤= words.length ≤= 100
• 1 ≤= words[i].length ≤= 12
• words[i] consists of lowercase English letters only
• Time complexity should be O(n * m) where n is the number of words and m is the average word length
• Space complexity should be O(n * m) for storing the unique transformations

Examples

Example 1:

` Input: words = ["gin", "zen", "gig", "msg"] Output: 2 Explanation:

• "gin" -> "--...-.."
• "zen" -> "--...-.."
• "gig" -> "--...--."
• "msg" -> "--...--." Only 2 distinct transformations exist. `

Example 2:

Input: words = ["a"] Output: 1 Explanation: Single word produces one unique transformation: ".-"

Example 3:

` Input: words = ["hello", "world"] Output: 2 Explanation:

• "hello" -> "......-..-.-.---"
• "world" -> ".------.-...-.." Both words produce different Morse code sequences. `

Hint 1: Data Structure for Uniqueness Use a set data structure to automatically handle deduplication of Morse code strings. As you transform each word, add its Morse representation to the set, which will only keep unique values.

Hint 2: Efficient Mapping Store the Morse code alphabet in a list or array indexed by letter position. You can convert a character to its index using ord(char) - ord('a') in Python, allowing quick lookup of each letter's Morse code.

Hint 3: String Building For each word, iterate through its characters, look up each character's Morse code, and concatenate them together. This can be done efficiently using string concatenation or join operations.

Full Solution ` def uniqueMorseRepresentations(words): # Morse code mapping for letters a-z morse = [ ".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.." ]

# Set to store unique transformations
transformations = set()

# Transform each word and add to set
for word in words:
    # Build the Morse code for this word
    morse_code = ""
    for char in word:
        # Get index of character (a=0, b=1, etc.)
        index = ord(char) - ord('a')
        morse_code += morse[index]
    
    # Add the transformation to our set
    transformations.add(morse_code)

# Return the count of unique transformations
return len(transformations)

`

Approach:

1. Morse Code Storage: We store the Morse code representations in a list indexed from 0-25, corresponding to letters a-z. This allows O(1) lookup for each letter.
2. Set for Uniqueness: We use a set to store the Morse code transformations. Sets automatically handle deduplication, so even if multiple words produce the same Morse code, it will only be stored once.
3. Character-by-Character Transformation: For each word, we iterate through its characters, convert each to its array index using ord(char) - ord('a'), lookup the corresponding Morse code, and concatenate it to build the complete transformation.
4. Result: After processing all words, the size of the set gives us the count of unique transformations.

Time Complexity: O(n * m) where n is the number of words and m is the average length of each word. We iterate through each word once and process each character.

Space Complexity: O(n * m) in the worst case where all words produce unique Morse code strings, requiring storage for each transformation in the set.

Alternative Implementation (More Pythonic):

` def uniqueMorseRepresentations(words): morse = [".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.."]

return len({
    ''.join(morse[ord(c) - ord('a')] for c in word)
    for word in words
})

`

This one-liner solution uses set comprehension and join to achieve the same result more concisely.