Leetcode 804. Unique Morse Code Words

Problem Explanation:

This problem follows the principle of encoding and then counting unique transformations. International Morse code is a technique for encoding each English character in a sequence of dots and dashes. Here, we are given a list of words with alphabets. Our task is to convert every word into Morse code, it means each letter of word should be converted into the corresponding Morse code followed by joining all Morse codes, which will be the transformation of the current word. From the whole transformation list, we need to return count of unique transformations.

Let's consider an example.

Example: Assume we have a list of words: ['gin', 'zen', 'gig', 'msg']. The Morse code of each word is as follows:

• 'gin' translates to "--...-."
• 'zen' translates to "--...-."
• 'gig' translates to "--...--."
• 'msg' translates to "--...--."

As we can see, after the transformations, we ended up with two unique Morse codes: "--...-." and "--...--.". So, the output will be 2.

Solution approach:

We start by creating a list (or array) of Morse codes for all English alphabets. Define a set to maintain all unique transformation. For each word in the given list of words, we take its each character and map it to Morse code (we can get Morse code of a character by its index in Morse code list) followed by joining them to get the transformation of that word. Store the transformation of each word in set. At the end, return the size of set (set only stores unique items).

Python Solution:

1
2python
3class Solution:
4    def uniqueMorseRepresentations(self, words):
5        morse = [".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", 
6                 ".---", "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", 
7                 "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.."]
8        transformations = set()
9        for word in words:
10            transformation = ""
11            for char in word:
12                transformation += morse[ord(char) - ord('a')]
13            transformations.add(transformation)
14        return len(transformations)

Java Solution:

1
2java
3class Solution {
4    public int uniqueMorseRepresentations(String[] words) {
5        String[] morse = {".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", 
6                          ".---", "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", 
7                          "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.."};
8        Set<String> transformations = new HashSet<String>();
9        for (String word : words) {
10            String transformation = "";
11            for (char c : word.toCharArray())
12                transformation += morse[c - 'a'];
13            transformations.add(transformation);
14        }
15        return transformations.size();
16    }
17}

Javascript Solution:

1
2javascript
3var uniqueMorseRepresentations = function(words) {
4    let morse = [".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..",
5                 ".---", "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.",
6                 "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.."];
7    let transformations = new Set();
8    for (let word of words) {
9        let transformation = "";
10        for (let char of word)
11            transformation += morse[char.charCodeAt(0) - 'a'.charCodeAt(0)];
12        transformations.add(transformation);
13    }
14    return transformations.size;
15};

C++ Solution:

1
2cpp
3class Solution {
4public:
5    int uniqueMorseRepresentations(vector<string>& words) {
6        vector<string> morse{".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", 
7                             ".---", "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", 
8                             "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.."};
9        unordered_set<string> transformations;
10        for (const string& word : words) {
11            string transformation;
12            for (const char c : word)
13                transformation += morse[c - 'a'];
14            transformations.insert(transformation);
15        }
16        return transformations.size();
17    }
18};

C# Solution:

1
2csharp
3public class Solution {
4    public int UniqueMorseRepresentations(string[] words) {
5        string[] morse = {".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..",
6                          ".---", "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.",
7                          "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.."};
8        HashSet<string> transformations = new HashSet<string>();
9        foreach (string word in words) {
10            string transformation = "";
11            foreach (char c in word)
12                transformation += morse[c - 'a'];
13            transformations.Add(transformation);
14        }
15        return transformations.Count;
16    }
17}

Ruby Solution:

In Ruby, we can use the map function to iterate through the array of words and transform them into Morse code. We then use uniq function to extract the unique Morse code representations of words and return their count with the size function.

1
2ruby
3def unique_morse_representations(words)
4  morse = [".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..",
5              ".---", "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.",
6              "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.."]
7  transformations = words.map { |word| word.chars.map { |char| morse[char.ord - 'a'.ord] }.join }
8  transformations.uniq.size
9end

Swift Solution:

In Swift, we start by defining a dictionary to map each character to its corresponding Morse code. We then use map and reduce to convert each word, and store the results in a Set to remove duplicates and count the unique representations.

1
2swift
3func uniqueMorseRepresentations(_ words: [String]) -> Int {
4    let morse = [".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..",
5                 ".---", "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.",
6                 "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.."]
7    var transformations = Set<String>()
8    words.forEach { word in 
9        let transformation = word.reduce("", { $0 + morse[Int($1.asciiValue! - 97)] })
10        transformations.insert(transformation)
11    }
12    return transformations.count
13}

Go Solution:

The Go solution also follows the similar pattern. We loop over each word, convert it to Morse code, and add it to a map. Finally, we return the size of the map.

1
2go
3func uniqueMorseRepresentations(words []string) int {
4    morse := [".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..",
5              ".---", "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.",
6              "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.."]
7    transformations := make(map[string]bool)
8    for _, word := range words {
9        transformation := ""
10        for _, char := range word {
11            transformation += morse[char - 'a']
12        }
13        transformations[transformation] = true
14    }
15    return len(transformations)
16}

These solutions all have a time complexity of O(n), where n is the total number of characters across all words, and a space complexity of O(1) as the Morse code map and transformation set sizes are constant regardless of the input size.