804. Unique Morse Code Words
Model: qwen2.5-coder:14b
Topics:
FAANG asked: 0
Acceptance rate: 79.0%
Problem Breakdown
The problem asks us to determine the number of unique Morse code transformations for a given list of words. Each letter in a word is converted to its corresponding Morse code representation, and the entire word is transformed by concatenating these Morse codes. The goal is to count how many distinct transformations exist among all the words.
Inputs:
- A list of words (
words), where each word consists of lowercase English letters.
Outputs:
- An integer representing the number of unique Morse code transformations.
Implicit Constraints or Edge Cases:
- The list
wordscan be empty, in which case the output should be 0. - Words can have varying lengths from 1 to 12 characters.
- All characters in each word are lowercase letters.
Intuition
A brute-force approach would involve converting each word to its Morse code transformation and storing these transformations in a list. We could then count the number of unique transformations by checking for duplicates, which might be done using a set. However, this approach is straightforward but not optimal in terms of space complexity since we store all transformations.
The key insight is that we can use a set to directly store each transformation as it’s computed, ensuring uniqueness automatically. This avoids the need to first collect all transformations and then filter out duplicates, thus saving space.
Approach
- Mapping Morse Code: Create a mapping from each letter (‘a’ to ‘z’) to its corresponding Morse code representation.
- Transformation Function: Define a function that takes a word and returns its Morse code transformation by concatenating the Morse codes of its letters.
- Unique Transformations Set: Use a set to store transformations as they are computed for each word in the input list.
- Count Unique Transformations: The size of the set at the end will give us the number of unique transformations.
Complexity Analysis
- Time Complexity: O(n * m), where n is the number of words and m is the average length of a word. This is because we need to process each character in each word.
- Space Complexity: O(n * m) for storing the Morse code transformations in the set, assuming all transformations are unique.
Solution
def uniqueMorseRepresentations(words):
morse_code_map = [".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..", "--",
"-.", "---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.."]
def word_to_morse(word):
return ''.join(morse_code_map[ord(char) - ord('a')] for char in word)
unique_transformations = set()
for word in words:
transformation = word_to_morse(word)
unique_transformations.add(transformation)
return len(unique_transformations)
# Example usage
words = ["gin", "zen", "gig", "msg"]
print(uniqueMorseRepresentations(words)) # Output: 2
Edge Cases Handled
- Empty Input: If the input list
wordsis empty, the function returns 0 immediately since there are no words to transform. - Single Word: The function correctly handles a single word by returning either 1 (if unique) or 0 (if not).
- All Identical Words: If all words in the list have the same transformation, the function returns 1.
- Distinct Transformations: The function efficiently counts distinct transformations even if there are many different words.