algoadvance

Leetcode 804. Unique Morse Code Words

Problem Statement

The problem states that we are given an array of words, where each word can be converted into a Morse code string based on the given mapping of each letter to a Morse code character. Our task is to determine how many different Morse code transformations we can get from the given array of words.

Each letter has a corresponding Morse code and the mapping is as follows:

'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 words, we need to return the number of unique Morse code transformations among them.

Clarifying Questions

1. Input Format:
   • Q: What is the format of the input?
   • A: The input is an array of strings, words.
2. Output Format:
   • Q: What is the format of the output?
   • A: The output is a single integer indicating the number of unique Morse code transformations.
3. Constraints:
   • Q: Are there any constraints on the length of the words or the number of words?
   • A: The length of a word is 1 ≤ length ≤ 12 and the number of words is 1 ≤ words.length ≤ 100.

Strategy

1. Data Structure:
   • We will use a HashSet to keep track of unique Morse code transformations as sets inherently ignore duplicates.
2. Algorithm:
   • Create an array of Morse code representations for each letter.
   • Iterate over each word in the input array.
   • Convert each character of the word to its Morse code equivalent using the array.
   • Concatenate these Morse codes to form the transformation for the word.
   • Add the transformation to our HashSet.
   • Return the size of the HashSet as it would give us the count of unique transformations.

Code

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

public class UniqueMorseCodeWords {
    public int uniqueMorseRepresentations(String[] words) {
        // Morse code for each letter a-z
        String[] morseCodes = new String[]{
            ".-","-...","-.-.","-..",".","..-.",
            "--.","....","..",".---","-.-",".-..",
            "--","-.","---",".--.","--.-",".-.",
            "...","-","..-","...-",".--","-..-",
            "-.--","--.."
        };

        // Using a HashSet to keep track of unique morse transformations
        Set<String> uniqueTransformations = new HashSet<>();

        // Iterate through each word
        for (String word : words) {
            StringBuilder transformation = new StringBuilder();

            // Convert each character to its corresponding morse code
            for (char c : word.toCharArray()) {
                transformation.append(morseCodes[c - 'a']);
            }

            // Add the transformation to the set
            uniqueTransformations.add(transformation.toString());
        }

        // The number of unique transformations
        return uniqueTransformations.size();
    }

    // Example usage
    public static void main(String[] args) {
        UniqueMorseCodeWords solution = new UniqueMorseCodeWords();
        String[] words = {"gin", "zen", "gig", "msg"};
        System.out.println(solution.uniqueMorseRepresentations(words)); // Output: 2
    }
}

Time Complexity

• Conversion of each word to Morse code: O(L) where L is the length of the word.
• Iterating through words: O(N) where N is the number of words.
• Overall Time Complexity: O(N * L), since for each word we are doing an O(L) operation, and we have N words. Given the constraints, this should efficiently handle the input sizes specified.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?