# LeetCode 804: Unique Morse Code Words

## Problem Restatement

We are given an array of lowercase English words.

Each letter can be converted into Morse code. A word is transformed by replacing every letter with its Morse code and concatenating the results into one string.

For example, the word `"cab"` becomes:

```python
"-.-." + ".-" + "-..." = "-.-..--..."
```

We need to return how many different transformed strings appear among all words. The task is to count unique transformations, not unique original words. The official problem defines the transformation this way and asks for the number of different transformations among all words.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A list of lowercase English words |
| Output | Number of distinct Morse code transformations |
| Letter mapping | Each lowercase letter `a` to `z` has a fixed Morse code |
| Main operation | Convert each word into one concatenated Morse string |

## Examples

Example:

```python
words = ["gin", "zen", "gig", "msg"]
```

The transformations are:

| Word | Morse Transformation |
|---|---|
| `"gin"` | `"--...-.."` |
| `"zen"` | `"--...-.."` |
| `"gig"` | `"--...--."` |
| `"msg"` | `"--...--."` |

There are only two different transformations:

```python
"--...-.."
"--...--."
```

So the answer is:

```python
2
```

Another example:

```python
words = ["a"]
```

The word `"a"` transforms to:

```python
".-"
```

There is one unique transformation, so the answer is:

```python
1
```

## First Thought: Direct Conversion

The problem already gives us a fixed mapping from letters to Morse code.

So the direct approach is:

1. Convert each word into Morse code.
2. Store the converted string.
3. Count how many different converted strings we have.

This is exactly what a set is for.

A set keeps only unique values. If two words produce the same Morse transformation, the set stores that transformation once.

## Key Insight

The original word does not matter after conversion.

For example:

```python
"gin" -> "--...-.."
"zen" -> "--...-.."
```

These are different words, but they produce the same transformation.

Since we only need the number of different transformations, we can insert every transformed word into a set and return the set size.

## Algorithm

Create the Morse code table:

```python
codes = [
    ".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..",
    ".---", "-.-", ".-..", "--", "-.", "---", ".--.", "--.-",
    ".-.", "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.."
]
```

The index of each code matches the letter position:

| Letter | Index |
|---|---|
| `a` | `0` |
| `b` | `1` |
| `c` | `2` |
| `z` | `25` |

For each word:

1. Start with an empty list of Morse pieces.
2. For each character `ch`, compute:

```python
ord(ch) - ord("a")
```

3. Use that index to get the Morse code.
4. Join the pieces into one string.
5. Add the string to a set.

Return the size of the set.

## Correctness

Each character in every input word is a lowercase English letter, so it has exactly one Morse code in the table.

For a word, the algorithm processes its letters from left to right and appends the Morse code of each letter. Therefore, the produced string is exactly the transformation defined by the problem.

The algorithm inserts every transformation into a set. A set stores one copy of each distinct value, so duplicate transformations are counted once.

After all words are processed, the set contains exactly all different Morse transformations from the input. Therefore, returning the set size gives the required answer.

## Complexity

Let `L` be the total number of characters across all words.

| Metric | Value | Why |
|---|---|---|
| Time | `O(L)` | Each character is converted once |
| Space | `O(L)` | The set may store transformed strings for all words |

The Morse table has 26 entries, so it uses constant extra space.

## Implementation

```python
class Solution:
    def uniqueMorseRepresentations(self, words: list[str]) -> int:
        codes = [
            ".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..",
            ".---", "-.-", ".-..", "--", "-.", "---", ".--.", "--.-",
            ".-.", "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.."
        ]

        transformations = set()

        for word in words:
            morse = []

            for ch in word:
                index = ord(ch) - ord("a")
                morse.append(codes[index])

            transformations.add("".join(morse))

        return len(transformations)
```

## Code Explanation

The `codes` array stores the Morse code for each lowercase English letter:

```python
codes[0]   # Morse code for 'a'
codes[1]   # Morse code for 'b'
codes[25]  # Morse code for 'z'
```

For each word, we build its transformation:

```python
morse = []
```

For each character, we convert it to an index:

```python
index = ord(ch) - ord("a")
```

For example:

```python
ord("a") - ord("a") == 0
ord("b") - ord("a") == 1
ord("z") - ord("a") == 25
```

Then we append the corresponding Morse code:

```python
morse.append(codes[index])
```

After processing the whole word, we join all pieces:

```python
"".join(morse)
```

That complete transformation is inserted into the set:

```python
transformations.add("".join(morse))
```

Finally, the number of unique transformations is:

```python
len(transformations)
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.uniqueMorseRepresentations(["gin", "zen", "gig", "msg"]) == 2
    assert s.uniqueMorseRepresentations(["a"]) == 1
    assert s.uniqueMorseRepresentations(["a", "a"]) == 1
    assert s.uniqueMorseRepresentations(["a", "b", "c"]) == 3
    assert s.uniqueMorseRepresentations(["no", "on"]) == 2

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `["gin", "zen", "gig", "msg"]` | Checks duplicate transformations |
| `["a"]` | Minimum simple case |
| `["a", "a"]` | Same word repeated |
| `["a", "b", "c"]` | All transformations different |
| `["no", "on"]` | Same letters in different order can transform differently |