Unique Morse Code Words solution and explanation
Google
9 more videos on this problem
LeetCode Unique Morse Code Words Solution Explained - JavaNick White · 5:18 · 11K views
Unique Morse Code Words | Leet code 804 | Theory explained + Python codeSai Anish Malla · 5:45 · 2K views
Unique Morse Code Words | Live Coding with Explanation | Leetcode #804Algorithms Made Easy · 2:08 · 1K views
Unique Morse Code Words | unique morse code wordsNaresh Gupta · 4:59 · 1K views
[Easy] Unique Morse Code Words (leetcode #804, javascript, dictionaries, arrays)Build Things That Work · 27:16 · 610 views
Unique Morse Code Words - LeetCode Problem #804GuyWho LikesCS · 22:02 · 449 views
804. Unique Morse Code Words || DSA || Leetcode || Daily ChallengeLeetcode Daily Challenge · 5:07 · 389 views
LeetCode 804 : Unique Morse Code Words | Solution in JAVAAmit Manjarly · 6:21 · 329 views
Leetcode 804 - Unique Morse Code Words (JAVA, Solution Explain!)LC Bear · 6:38 · 314 views
LeetCode 804. [easy] Unique Morse Code WordsFrancesco Manicardi · 2:37 · 206 views
The problem
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.
Approach overview
Problem Overview: Each lowercase English letter maps to a Morse code sequence. For every word in the input array, convert each character to its Morse representation, concatenate the signals, and count how many unique transformations exist.
Approach 1: HashSet Approach (O(n * L) time, O(n) space)
The straightforward strategy stores every transformed word in a HashSet. Create a lookup table that maps each letter 'a' to 'z' to its Morse code string. Iterate through each word, build its Morse representation by appending the Morse string for each character, and insert the final string into the set. Since sets automatically remove duplicates, the final answer is simply the size of the set.
This approach relies on fast hash lookups and insertions, which average O(1). If n is the number of words and L is the average word length, constructing transformations takes O(n * L) time. The set may store up to n unique Morse strings, giving O(n) extra space. The method is simple, readable, and commonly used in problems involving uniqueness checks with a hash table.
Approach 2: Direct Array Mapping (O(n * L) time, O(n) space)
Instead of using a dictionary to map characters to Morse code, use a fixed array of size 26 where index 0 represents 'a', 1 represents 'b', and so on. Access the Morse string with morse[c - 'a']. This removes hash lookups during translation and replaces them with constant-time array indexing.
For each word, iterate through its characters, append the corresponding Morse code from the array, and insert the transformation into a set to track uniqueness. Array indexing is extremely fast and reduces overhead compared to map-based lookups. The complexity remains O(n * L) time because every character must still be processed, and the set still requires up to O(n) space.
This method is a good example of optimizing character mapping using fixed-size arrays, a common trick in array and string problems where the alphabet size is known.
Recommended for interviews: The Direct Array Mapping approach is usually preferred. It demonstrates awareness of constant-time character indexing and avoids unnecessary hash maps. The HashSet-based idea still shows solid understanding of uniqueness tracking, but the array mapping version is cleaner and slightly more efficient.
Approach 1: HashSet Approach
We can utilize a HashSet data structure to store the unique transformations. For each word, we can generate its Morse code transformation by replacing each character by its corresponding Morse code. We then add each transformation to the HashSet to automatically handle duplicates. The size of the HashSet at the end gives us the number of unique transformations.
def uniqueMorseRepresentations(words):
morse_map = [
".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.."
]
unique_transformations = set()
for word in words:
transformation = ''.join(morse_map[ord(c) - ord('a')] for c in word)
unique_transformations.add(transformation)
return len(unique_transformations)
words = ["gin", "zen", "gig", "msg"]
print(uniqueMorseRepresentations(words))import java.util.HashSet;
import java.util.Set;
public class UniqueMorseCode {
public static int uniqueMorseRepresentations(String[] words) {
String[] morseMap = { ".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.." };
Set<String> uniqueTransformations = new HashSet<>();
for (String word : words) {
StringBuilder transformation = new StringBuilder();
for (char c : word.toCharArray()) {
transformation.append(morseMap[c - 'a']);
}
uniqueTransformations.add(transformation.toString());
}
return uniqueTransformations.size();
}
public static void main(String[] args) {
String[] words = {"gin", "zen", "gig", "msg"};
System.out.println(uniqueMorseRepresentations(words));
}
}#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;
string morseMap[] = { ".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.." };
int uniqueMorseRepresentations(vector<string>& words) {
unordered_set<string> uniqueTransformations;
for(string word : words) {
string transformation = "";
for(char c : word) {
transformation += morseMap[c - 'a'];
}
uniqueTransformations.insert(transformation);
}
return uniqueTransformations.size();
}
int main() {
vector<string> words = {"gin", "zen", "gig", "msg"};
cout << uniqueMorseRepresentations(words) << endl;
return 0;
}const uniqueMorseRepresentations = function(words) {
const morseMap = [
".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.."
];
const uniqueTransformations = new Set();
for (const word of words) {
let transformation = '';
for (const char of word) {
transformation += morseMap[char.charCodeAt(0) - 97];
}
uniqueTransformations.add(transformation);
}
return uniqueTransformations.size;
};
const words = ["gin", "zen", "gig", "msg"];
console.log(uniqueMorseRepresentations(words));#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#define ALPHABET_SIZE 26
char* morseMap[] = { ".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.." };
unsigned long hash(char *str) {
unsigned long hash = 5381;
int c;
while ((c = *str++)) {
hash = ((hash << 5) + hash) + c;
}
return hash;
}
bool checkUnique(char *transformation, unsigned long *hashSet, int size, int *len) {
unsigned long hashValue = hash(transformation);
for(int i = 0; i < *len; i++) {
if(hashSet[i] == hashValue) {
return false;
}
}
hashSet[(*len)++] = hashValue;
return true;
}
int uniqueMorseRepresentations(char **words, int wordsSize) {
unsigned long *hashSet = (unsigned long *)malloc(wordsSize * sizeof(unsigned long));
int uniqueCount = 0;
for (int i = 0; i < wordsSize; i++) {
char transformation[100] = "";
char *word = words[i];
while (*word) {
strcat(transformation, morseMap[*word - 'a']);
word++;
}
if (checkUnique(transformation, hashSet, wordsSize, &uniqueCount)) {
// Word's transformation is unique
}
}
free(hashSet);
return uniqueCount;
}
int main() {
char *words[] = {"gin", "zen", "gig", "msg"};
int size = sizeof(words) / sizeof(words[0]);
printf("%d\n", uniqueMorseRepresentations(words, size));
return 0;
}using System;
using System.Collections.Generic;
class UniqueMorseCode {
public static int UniqueMorseRepresentations(string[] words) {
string[] morseMap = { ".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.." };
HashSet<string> uniqueTransformations = new HashSet<string>();
foreach (string word in words) {
string transformation = "";
foreach (char c in word) {
transformation += morseMap[c - 'a'];
}
uniqueTransformations.Add(transformation);
}
return uniqueTransformations.Count;
}
static void Main() {
string[] words = { "gin", "zen", "gig", "msg" };
Console.WriteLine(UniqueMorseRepresentations(words));
}
}In the Python version, we use a set to track unique Morse code transformations. As each word is processed, its corresponding Morse code is generated using list comprehension and joined into a string which is then added to the set. In the end, the size of the set indicates the count of unique transformations.
Time Complexity: O(N), where N is the total number of characters across all words.
Space Complexity: O(WL), where W is the number of words and L is the length of the longest word, due to the storage of transformations.
Approach 2: Direct Array Mapping
In this method, we establish a direct mapping of characters to Morse code using a fixed array index, which simplifies the translation process by utilizing the ASCII value difference between 'a' and the current character. We then use the translated words to populate a set directly, ensuring uniqueness of each transformation.
def uniqueMorseRepresentations(words):
morse_map = [
".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.."
]
unique_transformations = set()
for word in words:
transformation = ''.join(morse_map[ord(c) - ord('a')] for c in word)
unique_transformations.add(transformation)
return len(unique_transformations)
words = ["gin", "zen", "gig", "msg"]
print(uniqueMorseRepresentations(words))import java.util.HashSet;
import java.util.Set;
public class UniqueMorseCode {
public static int uniqueMorseRepresentations(String[] words) {
String[] morseMap = { ".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.." };
Set<String> uniqueTransformations = new HashSet<>();
for (String word : words) {
String transformation = "";
for (char c : word.toCharArray()) {
transformation += morseMap[c - 'a'];
}
uniqueTransformations.add(transformation);
}
return uniqueTransformations.size();
}
public static void main(String[] args) {
String[] words = {"gin", "zen", "gig", "msg"};
System.out.println(uniqueMorseRepresentations(words));
}
}#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;
string morseMap[] = { ".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.." };
int uniqueMorseRepresentations(vector<string>& words) {
unordered_set<string> uniqueTransformations;
for (string word : words) {
string transformation;
for (char c : word) {
transformation += morseMap[c - 'a'];
}
uniqueTransformations.insert(transformation);
}
return uniqueTransformations.size();
}
int main() {
vector<string> words = {"gin", "zen", "gig", "msg"};
cout << uniqueMorseRepresentations(words) << endl;
return 0;
}const uniqueMorseRepresentations = function(words) {
const morseMap = [
".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.."
];
const uniqueTransformations = new Set();
for (const word of words) {
let transformation = '';
for (const char of word) {
transformation += morseMap[char.charCodeAt(0) - 97];
}
uniqueTransformations.add(transformation);
}
return uniqueTransformations.size;
};
const words = ["gin", "zen", "gig", "msg"];
console.log(uniqueMorseRepresentations(words));#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char* morseMap[] = { ".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.." };
int uniqueMorseCodeWords(char **words, int wordsSize) {
char transformations[100][100];
int uniqueCount = 0;
for (int i = 0; i < wordsSize; i++) {
char transformation[100] = "";
for (int j = 0; j < strlen(words[i]); j++) {
strcat(transformation, morseMap[words[i][j] - 'a']);
}
int k;
for (k = 0; k < uniqueCount; k++) {
if (strcmp(transformations[k], transformation) == 0) {
break;
}
}
if (k == uniqueCount) {
strcpy(transformations[uniqueCount++], transformation);
}
}
return uniqueCount;
}
int main() {
char *words[] = {"gin", "zen", "gig", "msg"};
int size = sizeof(words) / sizeof(words[0]);
printf("%d\n", uniqueMorseCodeWords(words, size));
return 0;
}using System;
using System.Collections.Generic;
class UniqueMorseCode {
public static int UniqueMorseRepresentations(string[] words) {
string[] morseMap = { ".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.." };
HashSet<string> uniqueTransformations = new HashSet<string>();
foreach (string word in words) {
string transformation = "";
foreach (char c in word) {
transformation += morseMap[c - 'a'];
}
uniqueTransformations.Add(transformation);
}
return uniqueTransformations.Count;
}
static void Main() {
string[] words = { "gin", "zen", "gig", "msg" };
Console.WriteLine(UniqueMorseRepresentations(words));
}
}This Python function substitutes quickly, embracing ASCII logic to convert word characters into Morse, employing set() to deftly filter duplicates.
Time Complexity: O(N), elucidating all input characters uniformly.
Space Complexity: O(WL), letting transformations populate the set.
Approach 3: Default Approach
const codes = [
'.-',
'-...',
'-.-.',
'-..',
'.',
'..-.',
'--.',
'....',
'..',
'.---',
'-.-',
'.-..',
'--',
'-.',
'---',
'.--.',
'--.-',
'.-.',
'...',
'-',
'..-',
'...-',
'.--',
'-..-',
'-.--',
'--..',
];
function uniqueMorseRepresentations(words: string[]): number {
return new Set(
words.map(word => {
return word
.split('')
.map(c => codes[c.charCodeAt(0) - 'a'.charCodeAt(0)])
.join('');
}),
).size;
}func uniqueMorseRepresentations(words []string) int {
codes := []string{".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..", "--", "-.",
"---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.."}
s := make(map[string]bool)
for _, word := range words {
t := &strings.Builder{}
for _, c := range word {
t.WriteString(codes[c-'a'])
}
s[t.String()] = true
}
return len(s)
}use std::collections::HashSet;
impl Solution {
pub fn unique_morse_representations(words: Vec<String>) -> i32 {
const codes: [&str; 26] = [
".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..",
"--", "-.", "---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-",
"-.--", "--..",
];
words
.iter()
.map(|word| {
word.as_bytes()
.iter()
.map(|v| codes[(v - b'a') as usize])
.collect::<String>()
})
.collect::<HashSet<String>>()
.len() as i32
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| HashSet Approach | Time Complexity: O(N), where N is the total number of characters across all words. Space Complexity: O(WL), where W is the number of words and L is the length of the longest word, due to the storage of transformations. |
| Direct Array Mapping | Time Complexity: O(N), elucidating all input characters uniformly. Space Complexity: O(WL), letting transformations populate the set. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashSet with HashMap Mapping | O(n * L) | O(n) | General case when using a dictionary for character mapping is acceptable |
| Direct Array Mapping + HashSet | O(n * L) | O(n) | Preferred when alphabet size is fixed and fast array indexing is possible |
Frequently asked questions
Is Unique Morse Code Words easy or hard?
Unique Morse Code Words is categorized as an Easy problem on LeetCode. It mainly tests basic string manipulation, array indexing, and using a hash set to track unique values.
How to solve Unique Morse Code Words in O(n)?
The practical complexity is O(n * L) because each character must be translated to Morse code. Use an array of Morse representations for the alphabet and a HashSet to store transformations. Iterate through each word, build the Morse string, and count unique entries in the set.
What is the best approach for Unique Morse Code Words?
The best approach uses a fixed array of 26 Morse code strings and a HashSet to store unique transformations. For each word, convert characters to Morse using array indexing and add the resulting string to the set. This runs in O(n * L) time and O(n) space, where n is the number of words and L is the average word length.
What data structure is used in Unique Morse Code Words?
The primary data structure is a HashSet used to track unique Morse code transformations. An array of size 26 is also commonly used to map each lowercase English letter to its Morse code string efficiently.
What is the time complexity of Unique Morse Code Words?
The time complexity is O(n * L). Each of the n words is processed character by character, and building the Morse transformation requires iterating through L characters on average. HashSet insertions are O(1) on average, so they do not change the overall complexity.
Is Unique Morse Code Words asked at Google, Amazon, or Meta?
Unique Morse Code Words is a common beginner-level interview problem that tests hash set usage and string transformation. Variations of similar problems appear in interviews at companies like Amazon and Google, especially in early screening rounds.