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.
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(); }}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.