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:

1

[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]

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 differenttransformations among all words we have.

Examples

Example 1

1
2
3
4
5
6
7
8

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

1
2

Input: words = ["a"]
Output: 1

Constraints

  • 1 <= words.length <= 100
  • 1 <= words[i].length <= 12
  • words[i] consists of lowercase English letters.

Solution

Method 1 – Hash Set and String Transformation

Intuition

Transform each word to Morse code and count the number of unique transformations using a set.

Approach

  1. For each word, convert each letter to Morse code and concatenate.
  2. Add the transformation to a set.
  3. Return the size of the set.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

import java.util.*;
class Solution {
    public int uniqueMorseRepresentations(String[] words) {
        String[] morse = {".-","-...","-.-.","-..",".","..-.","--.","....","..",
            ".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-",
            "..-","...-",".--","-..-","-.--","--.."};
        Set<String> seen = new HashSet<>();
        for (String w : words) {
            StringBuilder sb = new StringBuilder();
            for (char c : w.toCharArray()) sb.append(morse[c - 'a']);
            seen.add(sb.toString());
        }
        return seen.size();
    }
}
1
2
3
4
5
6
7
8

def uniqueMorseRepresentations(words):
    morse = [".-","-...","-.-.","-..",".","..-.","--.","....","..",
        ".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-",
        "..-","...-",".--","-..-","-.--","--.."]
    seen = set()
    for w in words:
        seen.add(''.join(morse[ord(c)-ord('a')] for c in w))
    return len(seen)

Complexity

  • ⏰ Time complexity: O(n * k) — n = number of words, k = average word length.
  • 🧺 Space complexity: O(n) — For the set of unique transformations.