# Unique Morse Code Words
**Difficulty:** EASY
[External](https://leetcode.com/problems/unique-morse-code-words)
Canonical: https://scaleengineer.com/dsa/problems/unique-morse-code-words
**Data structures:** Array, Hash Table, String
**Companies:** [Wix](https://scaleengineer.com/companies/wix)
---
## 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 <= 100`
* `1 <= words[i].length <= 12`
* `words[i]` consists of lowercase English letters.

# Approaches
## Using a List, Sorting, and Counting
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
- 1. Define the Morse code mapping as a `String` array.
- 2. Create an `ArrayList<String>` to store all transformations.
- 3. Iterate through each `word` in the input array.
- 4. For each `word`, construct its Morse code transformation string using a `StringBuilder`.
- 5. Add the constructed transformation to the list.
- 6. After processing all words, sort the list of transformations. This brings identical strings adjacent to each other.
- 7. Iterate through the sorted list, comparing each element with the previous one to count the number of unique strings.
- 8. Return the final count.

## Using a HashSet to Store Unique Transformations
This is the most efficient approach. It involves generating the Morse code transformation for each word and adding it to a `HashSet`. The `HashSet` data structure automatically handles duplicates, ensuring that only unique transformations are stored. The final answer is simply the size of the `HashSet` after processing all the words.
**Time:** O(S), where S is the total number of characters across all words in the input array. For each character, we do a constant time lookup and an append operation. Adding a string of length `k` to a `HashSet` takes O(k) on average. Therefore, the total time is proportional to the sum of the lengths of all the generated transformation strings, which is O(S). · **Space:** O(S), where S is the total number of characters across all words. In the worst-case scenario, all transformations are unique, and the `HashSet` will need to store all of them. The total space required is proportional to the total length of all unique transformation strings.
**Pros:** Highly efficient, with a linear time complexity relative to the total input size.; Elegant and concise code, leveraging the properties of a `HashSet` to handle uniqueness automatically.; Requires only a single pass through the input words.
**Cons:** Requires understanding of hash sets and their time/space complexity.; The space complexity can be significant if there are many long, unique words, but this is inherent to the problem of storing the unique results.
### Explanation
We start by defining the Morse code mapping in a `String` array. We initialize a `HashSet<String>` which will store the unique transformations we encounter. We iterate through each `word` in the input `words` array. For each `word`, we use a `StringBuilder` to construct its transformation. We loop through the characters of the word, find the corresponding Morse code from our mapping array, and append it to the `StringBuilder`. Once the transformation for a word is built, we add the resulting string to our `HashSet`. The `add` operation of the `HashSet` will only add the element if it's not already present in the set. After iterating through all the words, the `HashSet` contains all the unique transformations. The number of different transformations is then simply the size of the `HashSet`, which we return.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int uniqueMorseRepresentations(String[] words) {
        String[] MORSE = new String[]{".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.- ",".-..","--","-.","---",".--.","--.-",".-.","...","-","..- ","...-",".--","-..-","-.--","--.."};
        
        Set<String> uniqueTransformations = new HashSet<>();
        
        for (String word : words) {
            StringBuilder transformation = new StringBuilder();
            for (char c : word.toCharArray()) {
                transformation.append(MORSE[c - 'a']);
            }
            uniqueTransformations.add(transformation.toString());
        }
        
        return uniqueTransformations.size();
    }
}
```
### Algorithm
- 1. Define the Morse code mapping as a `String` array.
- 2. Create a `HashSet<String>` to store unique transformations.
- 3. Iterate through each `word` in the input array.
- 4. For each `word`, construct its Morse code transformation string using a `StringBuilder`.
- 5. Add the constructed transformation to the `HashSet`. The set will automatically handle duplicates.
- 6. After the loop finishes, return the size of the `HashSet`.

# Solutions
### Java

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

```

### CPP

```cpp
class Solution {
public:
  int uniqueMorseRepresentations(vector<string> &words) {
    vector<string> codes = {
        ".-",   "-...", "-.-.", "-..",  ".",   "..-.", "--.",  "....", "..",
        ".---", "-.-",  ".-..", "--",   "-.",  "---",  ".--.", "--.-", ".-.",
        "...",  "-",    "..-",  "...-", ".--", "-..-", "-.--", "--.."};
    unordered_set<string> s;
    for (auto &word : words) {
      string t;
      for (char &c : word)
        t += codes[c - 'a'];
      s.insert(t);
    }
    return s.size();
  }
};

```

### Python

```python
class Solution:
    def uniqueMorseRepresentations(self, words: List[str]) -> int: codes = [".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--..", ] s = {'' . join([codes[ord(c) - ord('a')] for c in word]) for word in words} return len(s)

```