Unique Morse Code Words — Solution in Python, Java & C++
Unique Morse Code Words solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Unique Morse Code Words is an easy coding problem on arrays, strings and hash table, asked in Amazon and Google interviews.
- Difficulty: Easy
- Topics: Arrays, Strings, Hash Table
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Each lowercase letter maps to a Morse code string:
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 --..
The transformation of a word is the concatenation of its letters' codes — for example "cab" becomes "-.-..--...".
Given an array words, return the number of distinct transformations among them.
Example 1
Input: words = ["gin","zen","gig","msg"]
Output: 2
Explanation: "gin" and "zen" both encode to "--...-.", and "gig" and "msg" both encode to "--...--.".
Example 2
Input: words = ["a"]
Output: 1
Example 3
Input: words = ["a","b"]
Output: 2
Constraints
1 <= words.length <= 1001 <= words[i].length <= 12words[i] consists of lowercase English letters.
Hints for Unique Morse Code Words
Hint 1
Store the 26 codes in an array indexed by
letter - 'a'.Hint 2
Build each word's transformation by concatenating its letters' codes.
Hint 3
Push the results into a set and return its size.
How to solve Unique Morse Code Words
The transformation is a pure function of the word, so the answer is simply the size of the image set — a hash set does all the deduplication.
Approach
- Keep the 26 codes in a fixed lookup array in alphabet order.
- For each word, concatenate
MORSE[c - 'a']over its characters. - Insert every transformation into a set.
- Return the set's size.
Why it works
Two words collide exactly when their concatenated codes are identical, which is what set membership tests. Note Morse here is not prefix-free once concatenated, which is precisely why distinct words can collide.
Complexity
- Time —
O(total characters) - Space —
O(total characters) for the set
Pitfalls
- Comparing words pairwise is O(n²·L) and unnecessary.
- Inserting a separator between letter codes changes the answer — the concatenation must be raw.
- Getting even one code in the table wrong silently changes collisions.
Reference solution
Python
from typing import List
def uniqueMorseRepresentations(words: List[str]) -> int:
morse = [".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---",
"-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-",
"..-", "...-", ".--", "-..-", "-.--", "--.."]
seen = set()
for w in words:
seen.add(''.join(morse[ord(c) - 97] for c in w))
return len(seen)Java
public static int uniqueMorseRepresentations(String[] words) {
String[] morse = {".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---",
"-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-",
"..-", "...-", ".--", "-..-", "-.--", "--.."};
HashSet<String> seen = new HashSet<>();
for (String w : words) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < w.length(); i++) sb.append(morse[w.charAt(i) - 'a']);
seen.add(sb.toString());
}
return seen.size();
}C++
int uniqueMorseRepresentations(vector<string>& words) {
vector<string> morse = {".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---",
"-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-",
"..-", "...-", ".--", "-..-", "-.--", "--.."};
unordered_set<string> seen;
for (auto& w : words) {
string code;
for (char c : w) code += morse[c - 'a'];
seen.insert(code);
}
return (int) seen.size();
}JavaScript
var uniqueMorseRepresentations = function(words) {
const morse = [".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---",
"-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-",
"..-", "...-", ".--", "-..-", "-.--", "--.."];
const seen = {};
for (let i = 0; i < words.length; i++) {
let code = "";
for (let j = 0; j < words[i].length; j++) {
code += morse[words[i].charCodeAt(j) - 97];
}
seen[code] = true;
}
return Object.keys(seen).length;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.