Unique Morse Code Words
EasyPrompt
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 can be written as a concatenation of the Morse code of each letter.
- For example,
"cab"can be written as"-.-..--...", which is the concatenation of"-.-.",".-", and"-...". We will call such a concatenation the transformation of a word.
Return the number of different transformations among all words we have.
Example 1:
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 "--...--.".Example 2:
Input: words = ["a"]
Output: 1
Constraints:
1 <= words.length <= 1001 <= words[i].length <= 12words[i]consists of lowercase English letters.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves first generating the Morse code transformation for every word in the input list. All these transformations are stored in a list. To count the unique ones, the list is sorted, which brings all identical transformations together. Finally, a single pass over the sorted list is made to count the number of unique elements.
Algorithm
-
- Define the Morse code mapping as a
Stringarray.
- Define the Morse code mapping as a
-
- Create an
ArrayList<String>to store all transformations.
- Create an
-
- Iterate through each
wordin the input array.
- Iterate through each
-
- For each
word, construct its Morse code transformation string using aStringBuilder.
- For each
-
- Add the constructed transformation to the list.
-
- After processing all words, sort the list of transformations. This brings identical strings adjacent to each other.
-
- Iterate through the sorted list, comparing each element with the previous one to count the number of unique strings.
-
- Return the final count.
Walkthrough
First, we need a way to map letters to their Morse codes. A String array is a good choice, where the index c - 'a' corresponds to the character c. We initialize an ArrayList to store the generated Morse code strings. We iterate through each word in the input words array. For each word, we build its transformation by iterating through its characters, looking up the Morse code for each character, and concatenating them. After processing all words, we sort the list of transformations. This places all duplicate strings adjacent to each other. Finally, we iterate through the sorted list, comparing each element with the previous one to count the number of unique strings. The count starts at 1 (for the first element, assuming the list is not empty) and is incremented whenever a new, different string is encountered.
import java.util.ArrayList;import java.util.Collections;import java.util.List; class Solution { public int uniqueMorseRepresentations(String[] words) { String[] MORSE = new String[]{".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.- ",".-..","--","-.","---",".--.","--.-",".-.","...","-","..- ","...-",".--","-..-","-.--","--.."}; if (words == null || words.length == 0) { return 0; } List<String> transformations = new ArrayList<>(); for (String word : words) { StringBuilder sb = new StringBuilder(); for (char c : word.toCharArray()) { sb.append(MORSE[c - 'a']); } transformations.add(sb.toString()); } if (transformations.isEmpty()) { return 0; } Collections.sort(transformations); int uniqueCount = 1; for (int i = 1; i < transformations.size(); i++) { if (!transformations.get(i).equals(transformations.get(i-1))) { uniqueCount++; } } return uniqueCount; }}Complexity
Time
O(S + N * L * log N), where N is the number of words, L is the maximum length of a word, and S is the total number of characters in all words. Generating all transformations takes O(S) time. Sorting N strings of maximum length L*4 takes O(N * log N * L) time, as string comparisons take O(L) time. The final pass takes O(N * L). The sorting step dominates the complexity.
Space
O(S), where S is the total number of characters in all words. This space is required to store the list of all N transformations. The maximum length of a transformation is proportional to the length of the original word.
Trade-offs
Pros
Conceptually simple, using standard library components like lists and sorting.
Does not require knowledge of hash-based data structures.
Cons
Less efficient than the HashSet approach due to the expensive sorting step, which has a time complexity of O(N log N).
Involves multiple passes over the data: one to build the transformations, one to sort, and one to count the unique ones.
This is the most efficient approach. It involves generating the Morse code transformation for each word and adding it to a HashSet. The HashSet data structure automatically handles duplicates, ensuring that only unique transformations are stored. The final answer is simply the size of the HashSet after processing all the words.
Algorithm
-
- Define the Morse code mapping as a
Stringarray.
- Define the Morse code mapping as a
-
- Create a
HashSet<String>to store unique transformations.
- Create a
-
- Iterate through each
wordin the input array.
- Iterate through each
-
- For each
word, construct its Morse code transformation string using aStringBuilder.
- For each
-
- Add the constructed transformation to the
HashSet. The set will automatically handle duplicates.
- Add the constructed transformation to the
-
- After the loop finishes, return the size of the
HashSet.
- After the loop finishes, return the size of the
Walkthrough
We start by defining the Morse code mapping in a String array. We initialize a HashSet<String> which will store the unique transformations we encounter. We iterate through each word in the input words array. For each word, we use a StringBuilder to construct its transformation. We loop through the characters of the word, find the corresponding Morse code from our mapping array, and append it to the StringBuilder. Once the transformation for a word is built, we add the resulting string to our HashSet. The add operation of the HashSet will only add the element if it's not already present in the set. After iterating through all the words, the HashSet contains all the unique transformations. The number of different transformations is then simply the size of the HashSet, which we return.
import java.util.HashSet;import java.util.Set; class Solution { public int uniqueMorseRepresentations(String[] words) { String[] MORSE = new String[]{".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.- ",".-..","--","-.","---",".--.","--.-",".-.","...","-","..- ","...-",".--","-..-","-.--","--.."}; Set<String> uniqueTransformations = new HashSet<>(); for (String word : words) { StringBuilder transformation = new StringBuilder(); for (char c : word.toCharArray()) { transformation.append(MORSE[c - 'a']); } uniqueTransformations.add(transformation.toString()); } return uniqueTransformations.size(); }}Complexity
Time
O(S), where S is the total number of characters across all words in the input array. For each character, we do a constant time lookup and an append operation. Adding a string of length `k` to a `HashSet` takes O(k) on average. Therefore, the total time is proportional to the sum of the lengths of all the generated transformation strings, which is O(S).
Space
O(S), where S is the total number of characters across all words. In the worst-case scenario, all transformations are unique, and the `HashSet` will need to store all of them. The total space required is proportional to the total length of all unique transformation strings.
Trade-offs
Pros
Highly efficient, with a linear time complexity relative to the total input size.
Elegant and concise code, leveraging the properties of a
HashSetto handle uniqueness automatically.Requires only a single pass through the input words.
Cons
Requires understanding of hash sets and their time/space complexity.
The space complexity can be significant if there are many long, unique words, but this is inherent to the problem of storing the unique results.
Solutions
Solution
class Solution {public int uniqueMorseRepresentations(String[] words) { String[] codes = new String[]{ ".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.."}; Set<String> s = new HashSet<>(); for (String word : words) { StringBuilder t = new StringBuilder(); for (char c : word.toCharArray()) { t.append(codes[c - 'a']); } s.add(t.toString()); } return s.size(); }}class Solution {public: int uniqueMorseRepresentations(vector<string> &words) { vector<string> codes = { ".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.."}; unordered_set<string> s; for (auto &word : words) { string t; for (char &c : word) t += codes[c - 'a']; s.insert(t); } return s.size(); }};class Solution: def uniqueMorseRepresentations(self, words: List[str]) -> int: codes = [".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--..", ] s = {'' . join([codes[ord(c) - ord('a')] for c in word]) for word in words} return len(s)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.