804. Unique Morse Code Words

EasyArrayHash TableString

Problem Description

International Morse Code defines a standard encoding where each letter from 'a' to 'z' corresponds to a unique sequence of dots (represented by '.') and dashes (represented by '-'). The task is to determine the number of unique Morse code representations of a given list of words.

Each word in the array words is a sequence of English lowercase letters, and the goal is to transform each word into its Morse code equivalent and then count the number of unique Morse code representations in the array. For example, the word "cab" would be transformed into "-.-..--..." by concatenating the Morse code for 'c' ("-.-."), 'a' (".-"), and 'b' ("-...").

To provide a solution, we should follow these steps:

Convert each letter in a word to its corresponding Morse code by referencing the provided list.
Concatenate all the Morse code representations for the letters in the word to form the Morse code representation of the word.
Add the Morse code for each word to a set, which automatically filters out duplicates.
Finally, return the count of unique Morse code representations in the set.

Intuition

The intuition behind the solution is to use the uniqueness property of sets in Python. Sets in Python can only contain unique elements, so by using a set, we can automatically ensure that only unique Morse code transformations of words are counted.

Another important observation is that the Morse code for each letter can be directly accessed using the ASCII value of the letter. This is done by subtracting the ASCII value of 'a' from the ASCII value of the current letter, resulting in the index of the Morse code for that letter. For instance, 'c' - 'a' gives us the index of the Morse representation for the letter 'c'.

The steps in the solution code include:

Initialize an array with the Morse code representations for each of the 26 English lowercase letters.
Transform words into their Morse code equivalents using list comprehensions and string join operations.
Use a set to collect unique Morse code representations. Adding the transformations to the set ensures that duplicates are not counted.
Return the length of the set, which represents the number of unique Morse code representations among all words provided.

The simplicity of the solution results in an efficient approach to solving the problem with minimal additional storage space and only a single pass through the array of words.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

How does quick sort divide the problem into subproblems?

Divide the array into two equal halves by indexDivide the array into two based on whether an element is smaller than an arbitrary valueDivide the array into a stray element and the rest of the arrayQuick sort does not use divide and conquer

I don’t know

Solution Approach

The solution to this problem involves a simple yet effective algorithm that mainly leverages Python's set data structure and array indexing.

Step-by-Step Implementation:

Array of Morse Code Representations: An array codes is initialized to store the Morse code for each letter. This array follows the sequence of the English alphabet from 'a' to 'z'.
Conversion to Morse Code: For each word in the words array, we convert it to its Morse code representation. This is achieved by iterating over each character in the word, finding its index in the alphabet (by subtracting the ASCII value of 'a' from the ASCII value of the letter), and then looking up the corresponding Morse code in the codes array.
String Concatenation: Python's join operation is used to concatenate the individual Morse codes into a single string representing the entire word.
Set for Uniqueness: A set s is employed to store the unique Morse code transformations of the words. As each Morse code string is created from a word, it is added to the set using a set comprehension. If the string is already in the set, it won't be added again, thus maintaining only unique entries.
Count Unique Representations: Finally, the length of the set s is returned. Since sets do not contain duplicates, the length of the set directly corresponds to the number of unique Morse code transformations.

Data Structures Used:

Array: The Morse code representations are stored in an array where each index corresponds to a letter in the English alphabet.
Set: A set is used to automatically handle the uniqueness of the Morse code transformations. Its properties ensure that it only contains unique Morse code strings.

Algorithmic Patterns Used:

Lookup: This approach uses a simple lookup pattern where Morse codes are accessed via indices based on character ASCII values.
Set Comprehension: The solution takes advantage of set comprehensions to build the set of unique Morse code transformations in a concise and readable way.

In summary, the algorithm converts each word to its Morse code representation, collects these into a set to filter out duplicates, and counts the number of elements in the set to determine the number of unique Morse code transformations.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following shows the order of node visit in a Breadth-first Search?

I don’t know

Example Walkthrough

Let's take a set of words ["gin", "zen", "gig", "msg"] and walk through the solution approach to determine the unique Morse code representations:

Array of Morse Code Representations: First, we prepare the codes array with the Morse code for each letter:

1codes = [".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-", ".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-", ".--","-..-","-.--","--.."]

Conversion to Morse Code: Next, for each word in ["gin", "zen", "gig", "msg"], we convert it into Morse code. For example:
- Taking "gin", we'll find the index for 'g', 'i', 'n' which are 6, 8, 13 respectively (0-indexed). Their Morse codes are "--.", "..", "-.".
- Concatenate them together to get the Morse representation for "gin": --...-..
String Concatenation: Repeat the process for the other words:
- "zen" becomes --...-.
- "gig" becomes --...--.
- "msg" becomes --...--..
Set for Uniqueness: Now, let's add each Morse code representation of the words to a set s:
```
1s = {"--...-.", "--...-.", "--...--.", "--...--."}
```
Note that the Morse codes for "gin" and "zen" are identical, as are those for "gig" and "msg", which the set will automatically consolidate.
Count Unique Representations: Lastly, we determine the unique Morse code representations by the count of the set s. In this case, the set reduces to {"--...-.", "--...--."}, which has a length of 2.

The output for this set of words is 2, meaning there are two unique Morse code representations among the provided words.

Solution Implementation

1class Solution:
2    def uniqueMorseRepresentations(self, words: List[str]) -> int:
3        # Define the Morse code representations for each lowercase alphabet letter
4        morse_codes = [".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", 
5                       "..", ".---", "-.-", ".-..", "--", "-.", "---", ".--.", 
6                       "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-", 
7                       "-.--", "--.."]
8
9        # Use a set to store unique Morse code transformations of the words
10        unique_transformations = set()
11
12        # Loop through each word in the provided list of words
13        for word in words:
14            # Transform the word into a Morse code representation
15            morse_word = ''.join([morse_codes[ord(char) - ord('a')] for char in word])
16            # Add the transformed Morse code word to the set of unique transformations
17            unique_transformations.add(morse_word)
18
19        # Return the count of unique Morse code transformations
20        return len(unique_transformations)
21

1// Solution class to find the number of unique Morse code representations from a list of words.
2class Solution {
3    public int uniqueMorseRepresentations(String[] words) {
4        // Array of Morse code representations for each letter from a to z.
5        String[] morseCodes = new String[] {
6            ".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....",
7            "..", ".---", "-.-", ".-..", "--", "-.", "---", ".--.",
8            "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-", 
9            "-.--", "--.."
10        };
11      
12        // Set to store unique Morse code transformations of the words.
13        Set<String> uniqueTransformations = new HashSet<>();
14      
15        // Iterate through each word in the input list.
16        for (String word : words) {
17            // StringBuilder to accumulate Morse code for the current word.
18            StringBuilder morseWord = new StringBuilder();
19          
20            // Convert each character in the word to its corresponding Morse code.
21            for (char ch : word.toCharArray()) {
22                morseWord.append(morseCodes[ch - 'a']); // Subtract 'a' to get the index.
23            }
24          
25            // Add the Morse code transformation to the set.
26            uniqueTransformations.add(morseWord.toString());
27        }
28      
29        // Return the size of the set, which is the number of unique Morse representations.
30        return uniqueTransformations.size();
31    }
32}
33

1#include <string>
2#include <vector>
3#include <unordered_set>
4
5class Solution {
6public:
7    // Function to count the unique Morse code representations for a list of words.
8    int uniqueMorseRepresentations(vector<string>& words) {
9        // Array of Morse code representations for each alphabet character.
10        vector<string> morseCodes = {
11            ".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---",
12            "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-",
13            "..-", "...-", ".--", "-..-", "-.--", "--.."
14        };
15
16        // Using a set to store unique Morse code transformations of the words.
17        // Sets in C++ are generally ordered; unordered_set is typically more efficient.
18        unordered_set<string> uniqueTransforms;
19      
20        // Loop over each word in the list of words.
21        for (const auto& word : words) {
22            string transformedWord;
23            // Loop over each character in the word and convert to Morse code.
24            for (const char& letter : word) {
25                // Append the corresponding Morse code for the character to the transformed word string.
26                // 'a' has an ASCII value of 97, so 'a' - 'a' will be 0, 'b' - 'a' will be 1, and so on,
27                // thus mapping characters to correct Morse code strings.
28                transformedWord += morseCodes[letter - 'a'];
29            }
30            // Insert the transformed word into the set.
31            uniqueTransforms.insert(transformedWord);
32        }
33
34        // The size of the set represents the number of unique Morse code transformations.
35        // Sets do not allow duplicate elements, so the count will only be of unique items.
36        return uniqueTransforms.size();
37    }
38};
39

1// Morse code representations for the 26 letters of the English alphabet.
2const morseCodes = [
3    '.-',   // a
4    '-...', // b
5    '-.-.', // c
6    '-..',  // d
7    '.',    // e
8    '..-.', // f
9    '--.',  // g
10    '....', // h
11    '..',   // i
12    '.---', // j
13    '-.-',  // k
14    '.-..', // l
15    '--',   // m
16    '-.',   // n
17    '---',  // o
18    '.--.', // p
19    '--.-', // q
20    '.-.',  // r
21    '...',  // s
22    '-',    // t
23    '..-',  // u
24    '...-', // v
25    '.--',  // w
26    '-..-', // x
27    '-.--', // y
28    '--..', // z
29];
30
31/**
32 * Converts an array of English words to their unique Morse code representations
33 * and returns the count of unique Morse code strings.
34 * @param {string[]} words - The array of words to be converted into Morse code.
35 * @return {number} - The count of unique Morse code representations.
36 */
37function uniqueMorseRepresentations(words: string[]): number {
38    // Transform each word into its Morse code representation
39    // and store the unique Morse code strings in a Set.
40    const uniqueMorseTransformations = new Set(
41        words.map(word => {
42            return word
43                // Split each word into characters.
44                .split('')
45                // Convert each character to its corresponding Morse code.
46                .map(character => morseCodes[character.charCodeAt(0) - 'a'.charCodeAt(0)])
47                // Join the Morse code sequence to get the word's Morse representation.
48                .join('');
49        })
50    );
51
52    // Return the size of the set, which represents the count of unique Morse code strings.
53    return uniqueMorseTransformations.size;
54}
55

Not Sure What to Study? Take the 2-min Quiz：

Which type of traversal does breadth first search do?

Pre-order traversalPost-order traversalIn-order traversalLevel-order traversal

I don’t know

Time and Space Complexity

Time Complexity

The time complexity of the code can be analyzed as follows:

There is one list, codes, that maps each letter of the English lowercase alphabet to its corresponding Morse code representation. This list is initialized only once, and this operation is O(1) because the size of the Morse code alphabet (and hence the list) is constant and does not scale with the size of the input.
The main operation is the set comprehension {... for word in words}, which iterates over each word in words.

For each word:

Iterating over each character in the word takes O(n) time, where n is the length of the word.
Accessing the Morse code for each character is an O(1) operation.
Joining the Morse codes to form a single string has a time complexity of O(m), where m is the total length of the Morse code for the word, which is linear in the length of the word.

Assuming w is the number of words and the average length of a word is represented as avg_len, then the time complexity becomes O(w * avg_len). For w iterations, and avg_len being the average time per iteration.

Space Complexity

The space complexity can be analyzed as follows:

The list codes has a fixed size (constant space) of 26 elements, which corresponds to the number of letters in the English alphabet. So, it is O(1).
The set s will contain at most w unique Morse representations if all words have unique Morse code translations. Since each word translates to a different length string based on its characters, let's denote max_morse_len as the maximum length of these Morse code strings for any word. Hence, the space complexity is O(w * max_morse_len).

Therefore, the overall space complexity of the function would be O(w * max_morse_len) reflecting the space needed to store the unique transformations.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

804. Unique Morse Code Words

Problem Description

Intuition

Solution Approach

Step-by-Step Implementation:

Data Structures Used:

Algorithmic Patterns Used:

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity