Difficulty: Easy | Acceptance: 83.60% | Paid: No Topics: Array, Hash Table, String
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 is written in the English alphabet, return the number of different transformations among all words we have.
- Examples
- Constraints
- Hash Set
- Brute Force List
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.
Hash Set
Intuition We can map each character in a word to its corresponding Morse code string using a predefined array. By concatenating these codes, we form the transformation for the word. To find the number of unique transformations, we can store each generated string in a Hash Set, which automatically handles uniqueness.
Steps
- Define the Morse code array for letters ‘a’ to ‘z’.
- Initialize an empty Hash Set to store unique transformations.
- Iterate through each word in the input list.
- For each word, iterate through its characters, look up the Morse code, and build the transformation string.
- Add the resulting transformation string to the Set.
- Return the size of the Set.
class Solution:
def uniqueMorseRepresentations(self, words: list[str]) -> int:
morse_codes = [".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....",
"..", ".---", "-.-", ".-..", "--", "-.", "---", ".--.",
"--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-",
"-.--", "--.."]
unique_transformations = set()
for word in words:
transformation = ""
for char in word:
# Map 'a' to index 0, 'b' to 1, etc.
index = ord(char) - ord('a')
transformation += morse_codes[index]
unique_transformations.add(transformation)
return len(unique_transformations)
Complexity
- Time: O(N * L) where N is the number of words and L is the average length of a word.
- Space: O(N * L) to store the unique transformations in the set.
- Notes: This is the most efficient approach for this problem.
Brute Force List
Intuition Instead of using a Hash Set, we can use a simple list or array to store the transformations. For each new transformation, we check if it already exists in the list. If it does not, we add it. This simulates the behavior of a Set without using built-in hashing.
Steps
- Define the Morse code array.
- Initialize an empty list to store unique transformations.
- Iterate through each word.
- Build the Morse code string for the word.
- Check if the string exists in the list.
- If it does not exist, append it to the list.
- Return the length of the list.
class Solution:
def uniqueMorseRepresentations(self, words: list[str]) -> int:
morse_codes = [".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....",
"..", ".---", "-.-", ".-..", "--", "-.", "---", ".--.",
"--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-",
"-.--", "--.."]
unique_transformations = []
for word in words:
transformation = ""
for char in word:
index = ord(char) - ord('a')
transformation += morse_codes[index]
if transformation not in unique_transformations:
unique_transformations.append(transformation)
return len(unique_transformations)
Complexity
- Time: O(N² * L) in the worst case, where N is the number of words and L is the average length. Checking if a string exists in a list takes O(N) time.
- Space: O(N * L) to store the transformations.
- Notes: This approach is less efficient than using a Hash Set due to the linear search time for duplicates.