Problem Description

You are given a mapping of each letter in the English alphabet (a-z) to its corresponding Morse code representation. The Morse code uses dots (.) and dashes (-) to encode each letter.

The mapping is provided as:

• 'a' → ".-"
• 'b' → "-..."
• 'c' → "-.-."
• And so on for all 26 letters

Given an array of strings words, you need to:

1. Convert each word to its Morse code representation by:

   • Taking each letter in the word
   • Looking up its Morse code equivalent
   • Concatenating all the Morse codes together (without spaces)

2. Count how many unique Morse code representations exist among all the transformed words.

For example:

• The word "cab" becomes "-.-..--..." because:
  • 'c' → "-.-."
  • 'a' → ".-"
  • 'b' → "-..."
  • Concatenated: "-.-." + ".-" + "-..." = "-.-..--..."

The solution works by:

1. Creating a list codes containing the Morse code for each letter in alphabetical order
2. For each word, transforming it to Morse code by:
   • Converting each character to its position in the alphabet using ord(c) - ord('a')
   • Using that position to look up the corresponding Morse code
   • Joining all the Morse codes together
3. Using a set comprehension to automatically eliminate duplicate transformations
4. Returning the size of the set, which represents the count of unique Morse code representations

Intuition

The key insight is that we need to count unique patterns, not unique words. Multiple different words might produce the same Morse code pattern, and we only want to count each pattern once.

Think about it this way: if we have words like "ab" and "d", they might produce different or identical Morse code patterns. We don't care about the original words anymore - we only care about how many distinct patterns we can create.

The natural approach is to:

1. Transform each word into its Morse code representation
2. Keep track of all the unique transformations we've seen

Since we're looking for unique values, a set is the perfect data structure. Sets automatically handle duplicates for us - if we try to add the same Morse code pattern twice, the set will only keep one copy.

The transformation itself is straightforward: for each letter in a word, we need to find its corresponding Morse code. Since the letters 'a' through 'z' map to indices 0 through 25, we can store the Morse codes in an array and use ord(c) - ord('a') to convert any lowercase letter to its index position.

For example, if we have the words ["gin", "zen", "gig", "msg"]:

• "gin" → "--...-.."
• "zen" → "--...-.."
• "gig" → "--...--."
• "msg" → "--...--."

Notice that "gin" and "zen" produce the same pattern, as do "gig" and "msg". So even though we have 4 words, we only have 2 unique Morse code representations.

By using a set to store all transformations and then returning its length, we elegantly solve the problem in one pass through the input.

Solution Approach

The implementation uses a set comprehension to efficiently transform and count unique Morse code representations.

Step 1: Define the Morse Code Mapping

First, we create an array codes where each index corresponds to a letter's position in the alphabet:

codes = [".-", "-...", "-.-.", "-..", ".", "...-", ...]

• Index 0 contains the Morse code for 'a'
• Index 1 contains the Morse code for 'b'
• And so on through index 25 for 'z'

Step 2: Transform Each Word Using Set Comprehension

The core logic is implemented in a single set comprehension:

s = {''.join([codes[ord(c) - ord('a')] for c in word]) for word in words}

Let's break this down from inside out:

1. Character to Index Conversion: ord(c) - ord('a')

   • For each character c in a word, calculate its alphabetical position
   • ord('a') - ord('a') = 0, ord('b') - ord('a') = 1, etc.

2. Morse Code Lookup: codes[ord(c) - ord('a')]

   • Use the calculated index to fetch the corresponding Morse code from the array

3. Word Transformation: [codes[ord(c) - ord('a')] for c in word]

   • Create a list of Morse codes for all characters in the word
   • For "cab": ['-.-.', '.-', '-...']

4. Concatenation: ''.join(...)

   • Join all Morse codes without any separator
   • ['-.-.', '.-', '-...'] becomes '-.-..--...'

5. Set Construction: {... for word in words}

   • Process all words and store results in a set
   • Duplicates are automatically eliminated

Step 3: Return the Count

return len(s)

The length of the set gives us the number of unique Morse code transformations.

Time Complexity: O(n * m) where n is the number of words and m is the average length of each word.

Space Complexity: O(n * m) for storing the unique transformations in the set.

Example Walkthrough

Let's walk through a small example with the words ["a", "b", "z", "a"].

Step 1: Set up the Morse code mapping

codes = [".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.."]

Step 2: Transform each word to Morse code

For word "a":

• Character 'a': ord('a') - ord('a') = 0
• Look up codes[0] = ".-"
• Morse representation: ".-"

For word "b":

• Character 'b': ord('b') - ord('a') = 1
• Look up codes[1] = "-..."
• Morse representation: "-..."

For word "z":

• Character 'z': ord('z') - ord('a') = 25
• Look up codes[25] = "--.."
• Morse representation: "--.."

For word "a" (second occurrence):

• Character 'a': ord('a') - ord('a') = 0
• Look up codes[0] = ".-"
• Morse representation: ".-"

Step 3: Collect unique transformations in a set

• Processing all words: {".-", "-...", "--..", ".-"}
• Since sets only keep unique values: {".-", "-...", "--.."}

Step 4: Count unique transformations

• len({".-", "-...", "--.."}) = 3

Even though we had 4 words, only 3 unique Morse code patterns exist because "a" appeared twice.

Let's try another example with ["gin", "zen"]:

For "gin":

• 'g': ord('g') - ord('a') = 6 → codes[6] = "--."
• 'i': ord('i') - ord('a') = 8 → codes[8] = ".."
• 'n': ord('n') - ord('a') = 13 → codes[13] = "-."
• Concatenate: "--." + ".." + "-." = "--...-.."

For "zen":

• 'z': ord('z') - ord('a') = 25 → codes[25] = "--.."
• 'e': ord('e') - ord('a') = 4 → codes[4] = "."
• 'n': ord('n') - ord('a') = 13 → codes[13] = "-."
• Concatenate: "--.." + "." + "-." = "--...-.."

Both words produce "--...-..", so the set contains only one unique pattern: {"--...-.."} Result: len({"--...-.."}) = 1

Solution Implementation

Time and Space Complexity

Time Complexity: O(n * m)

• n is the number of words in the input list
• m is the average length of each word
• For each word, we iterate through each character to build the Morse code representation
• The ord(c) - ord('a') operation is O(1) for each character
• String concatenation using ''.join() takes O(m) time for each word
• Set insertion is O(1) on average for each transformed word
• Overall: O(n * m) for processing all words

Space Complexity: O(n * m)

• The codes array is a constant with 26 elements: O(1)
• The set s can contain at most n unique Morse code representations
• Each Morse code representation has length proportional to the word length m
• In the worst case where all words produce unique Morse codes, we store n strings of average length m
• The list comprehension creates temporary strings for each word before adding to the set
• Overall: O(n * m) for storing the Morse code representations

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Character-to-Index Mapping

A common mistake is using the wrong formula to convert characters to array indices, such as:

• Using ord(c) - 'a' instead of ord(c) - ord('a') (mixing character and integer)
• Using ord(c) - ord('A') for lowercase letters (wrong ASCII offset)
• Forgetting to subtract ord('a') entirely and just using ord(c)

Example of incorrect code:

# Wrong: This will cause an IndexError
morse_representation = ''.join([morse_codes[ord(char)] for char in word])

# Wrong: This will cause a TypeError
morse_representation = ''.join([morse_codes[ord(char) - 'a'] for char in word])

Solution: Always use ord(char) - ord('a') to get the correct 0-based index for lowercase letters.

2. Using a List Instead of a Set

Some might accidentally use a list to store transformations and then try to count unique elements:

# Inefficient approach
transformations = []
for word in words:
    morse = ''.join([morse_codes[ord(c) - ord('a')] for c in word])
    if morse not in transformations:
        transformations.append(morse)
return len(transformations)

Solution: Use a set from the beginning to automatically handle duplicates and improve performance from O(n²) to O(n).

3. Adding Separators Between Morse Codes

Adding spaces or other separators between individual letter codes changes the problem:

# Wrong: adds spaces between morse codes
morse_representation = ' '.join([morse_codes[ord(c) - ord('a')] for c in word])

Solution: Use ''.join() with an empty string to concatenate without separators.

4. Handling Non-Lowercase or Non-Alphabetic Characters

If the input contains uppercase letters or non-alphabetic characters without proper validation:

# This will fail if word contains uppercase or special characters
morse = ''.join([morse_codes[ord(c) - ord('a')] for c in word])

Solution: Either validate input or normalize it:

# Convert to lowercase first if needed
morse = ''.join([morse_codes[ord(c.lower()) - ord('a')] for c in word if c.isalpha()])

5. Morse Code Array Index Mismatch

Ensuring the morse code array has exactly 26 elements in the correct order. Missing or misaligned codes will produce wrong results:

# Wrong: Missing some letters or wrong order
morse_codes = [".-", "-...", ".", "-..", "-.-.", ...]  # Wrong order

Solution: Double-check that the array has all 26 morse codes in alphabetical order from 'a' to 'z'.