Unique Morse Code Words

Easy
511.

Unique Morse Code Words

Unique Morse Code Words is an easy coding problem on arrays, strings and hash table, asked in Amazon and Google interviews.

Each lowercase letter maps to a Morse code string:

a .-      b -...    c -.-.    d -..     e .       f ..-.    g --.
h ....    i ..      j .---    k -.-     l .-..    m --      n -.
o ---     p .--.    q --.-    r .-.     s ...     t -       u ..-
v ...-    w .--     x -..-    y -.--    z --..

The transformation of a word is the concatenation of its letters' codes — for example "cab" becomes "-.-..--...".

Given an array words, return the number of distinct transformations among them.

Example 1

Input
words = ["gin","zen","gig","msg"]
Output
2
Explanation
"gin" and "zen" both encode to "--...-.", and "gig" and "msg" both encode to "--...--.".

Example 2

Input
words = ["a"]
Output
1

Example 3

Input
words = ["a","b"]
Output
2

Constraints

  • 1 <= words.length <= 100
  • 1 <= words[i].length <= 12
  • words[i] consists of lowercase English letters.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} words
 * @return {number}
 */
var uniqueMorseRepresentations = function(words) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Unique Morse Code Words — Solution in Python, Java & C++

Unique Morse Code Words solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Unique Morse Code Words is an easy coding problem on arrays, strings and hash table, asked in Amazon and Google interviews.

  • Difficulty: Easy
  • Topics: Arrays, Strings, Hash Table
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Each lowercase letter maps to a Morse code string:

a .-      b -...    c -.-.    d -..     e .       f ..-.    g --.
h ....    i ..      j .---    k -.-     l .-..    m --      n -.
o ---     p .--.    q --.-    r .-.     s ...     t -       u ..-
v ...-    w .--     x -..-    y -.--    z --..

The transformation of a word is the concatenation of its letters' codes — for example "cab" becomes "-.-..--...".

Given an array words, return the number of distinct transformations among them.

Example 1

Input: words = ["gin","zen","gig","msg"]
Output: 2
Explanation: "gin" and "zen" both encode to "--...-.", and "gig" and "msg" both encode to "--...--.".

Example 2

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

Example 3

Input: words = ["a","b"]
Output: 2

Constraints

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

Hints for Unique Morse Code Words

  1. Hint 1

    Store the 26 codes in an array indexed by letter - 'a'.

  2. Hint 2

    Build each word's transformation by concatenating its letters' codes.

  3. Hint 3

    Push the results into a set and return its size.

How to solve Unique Morse Code Words

The transformation is a pure function of the word, so the answer is simply the size of the image set — a hash set does all the deduplication.

Approach

  1. Keep the 26 codes in a fixed lookup array in alphabet order.
  2. For each word, concatenate MORSE[c - 'a'] over its characters.
  3. Insert every transformation into a set.
  4. Return the set's size.

Why it works

Two words collide exactly when their concatenated codes are identical, which is what set membership tests. Note Morse here is not prefix-free once concatenated, which is precisely why distinct words can collide.

Complexity

  • Time — O(total characters)
  • Space — O(total characters) for the set

Pitfalls

  • Comparing words pairwise is O(n²·L) and unnecessary.
  • Inserting a separator between letter codes changes the answer — the concatenation must be raw.
  • Getting even one code in the table wrong silently changes collisions.

Reference solution

Python

from typing import List

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

Java

public static int uniqueMorseRepresentations(String[] words) {
    String[] morse = {".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---",
        "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-",
        "..-", "...-", ".--", "-..-", "-.--", "--.."};
    HashSet<String> seen = new HashSet<>();
    for (String w : words) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < w.length(); i++) sb.append(morse[w.charAt(i) - 'a']);
        seen.add(sb.toString());
    }
    return seen.size();
}

C++

int uniqueMorseRepresentations(vector<string>& words) {
    vector<string> morse = {".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---",
        "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-",
        "..-", "...-", ".--", "-..-", "-.--", "--.."};
    unordered_set<string> seen;
    for (auto& w : words) {
        string code;
        for (char c : w) code += morse[c - 'a'];
        seen.insert(code);
    }
    return (int) seen.size();
}

JavaScript

var uniqueMorseRepresentations = function(words) {
    const morse = [".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---",
        "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-",
        "..-", "...-", ".--", "-..-", "-.--", "--.."];
    const seen = {};
    for (let i = 0; i < words.length; i++) {
        let code = "";
        for (let j = 0; j < words[i].length; j++) {
            code += morse[words[i].charCodeAt(j) - 97];
        }
        seen[code] = true;
    }
    return Object.keys(seen).length;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings