algoadvance

Leetcode 804. Unique Morse Code Words

Problem Statement:

The problem is to determine the number of unique Morse code transformations among a list of words. Each letter in a word can be transformed into its corresponding Morse code representation. The Morse code for each letter is given by a predefined table:

"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" -> "--.."

Given a list of words, you need to find out how many different transformations there are.

Clarifying Questions:

  1. Input Format: Is the input format always consistent with the list of lowercase words?
    • Yes, the input is always a list of lowercase words.
  2. Output Format: What should be the format of the output?
    • The output should be an integer representing the number of unique Morse code transformations.
  3. Word Constraints: What is the maximum length of words and the maximum number of words?
    • Typically, there might be constraints such as each word having a maximum length of 12, and there being a maximum of 1000 words in the list.

Strategy:

  1. Data Structures: Use a set to store unique Morse code transformations since sets inherently store only unique elements.
  2. Mapping Representation: Maintain a mapping of each English alphabet letter to its corresponding Morse code.
  3. Transformation Process:
    • Iterate through each word in the list.
    • For each word, concatenate the Morse code of each character to form the word’s Morse code transformation.
    • Insert the transformation into the set.
  4. Result: The size of the set will give the number of unique Morse code transformations.

Code:

#include <iostream>
#include <vector>
#include <unordered_set>
#include <string>

std::string morseMapping[26] = {
    ".-","-...","-.-.","-..",".","..-.",
    "--.","....","..",".---","-.-",".-..",
    "--","-.","---",".--.","--.-",".-.",
    "...","-","..-","...-",".--","-..-",
    "-.--","--.."
};

int uniqueMorseRepresentations(const std::vector<std::string>& words) {
    std::unordered_set<std::string> uniqueTransformations;
    
    for (const auto& word : words) {
        std::string morseWord;
        for (char c : word) {
            morseWord += morseMapping[c - 'a'];
        }
        uniqueTransformations.insert(morseWord);
    }
    
    return uniqueTransformations.size();
}

int main() {
    std::vector<std::string> words = {"gin", "zen", "gig", "msg"};
    std::cout << "Number of unique Morse code transformations: " 
              << uniqueMorseRepresentations(words) << std::endl;
    return 0;
}

Time Complexity:

This solution leverages the simplicity and uniqueness properties of sets to efficiently determine the number of unique Morse code transformations.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI