Introduction

In this blog post, we will explore how to solve the LeetCode problem "804" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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: [".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."] 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 different transformations among all words we have. Example 1: 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: Input: words = ["a"] Output: 1 Constraints: 1 <= words.length <= 100 1 <= words[i].length <= 12 words[i] consists of lowercase English letters.

Explanation

• Transformation Generation: Iterate through each word in the input array. For each word, build its Morse code transformation by concatenating the Morse code representations of its individual characters.
  • Uniqueness Tracking: Use a set data structure to store the generated transformations. Sets automatically handle duplicate elimination, ensuring that only unique transformations are counted.
  • Counting Unique Transformations: After processing all words, the size of the set represents the number of distinct transformations, which is the desired result.

• Runtime Complexity: O(N * M), where N is the number of words and M is the maximum length of a word.
• Storage Complexity: O(N), where N is the number of words (in the worst case where all transformations are unique).

Code

    def uniqueMorseRepresentations(words: list[str]) -> int:
    """
    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 different transformations among all words we have.

    Example 1:
    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:
    Input: words = ["a"]
    Output: 1

    Constraints:
    1 <= words.length <= 100
    1 <= words[i].length <= 12
    words[i] consists of lowercase English letters.
    """
    morse_codes = [".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.."]
    transformations = set()

    for word in words:
        transformation = ""
        for char in word:
            transformation += morse_codes[ord(char) - ord('a')]
        transformations.add(transformation)

    return len(transformations)