Quote from Wikipedia “Morse code is a method used in telecommunication to encode text characters as standardized sequences of two different signal durations, called dots and dashes, or dits and dahs. Morse code is named after Samuel Morse, one of the inventors of the telegraph.”. By the way, Samuel Morse was an American artist.

Problem: Unique Morse Code Words

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

Brute force 1

What came to my mind first is a brute force method.

The method is very straightforward.

1. It defines the Morese code mapping dictionary.
2. Loop through each word in the words list.
3. For each letter in the word, get its value by looking it up in the mapping dictionary
4. Glue back the word after getting its Morse code, and save it to a list if it is not already in the list
5. Return length of the list

codemorse_code_brute_force.py

mapping = dict(zip('abcdefghijklmnopqrstuvwxyz', [".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]))

def countWords(words, mapping):
    wordsmapped = []
    for w in words:
        wl = list(w)
        lmapped = []
        for letter in wl:
            lmapped.append(mapping[letter])

        wmapped = ''.join(lmapped)
        if wmapped not in wordsmapped:
            wordsmapped.append(wmapped)
    return len(wordsmapped)
    
words = ["gin","zen","gig","msg"]
print(countWords(words, mapping))
# 2

Brute force 2

This method has the same structure as brute force method 1. Both are using double loops.

1. The difference is using the difference of two ord() functions to find the position of the morse code that is corresponding to the English character.
2. It uses wmapped + instead of .join.

Although the use of ord() is clever, I still prefer brute force 1 because it is very straightforward and basic. You don’t have to think up the trick of using ord().

codemorse_code_brute_force.py

words = ["gin","zen","gig","msg"]
def uniqueMorseRepresentations(words):
    """
    :type words: List[str]
    :rtype: int
    """
    morse = [".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]
    
    wordsmapped = []
    
    for word in words:
        wmapped = ''
        for c in word:
            wmapped = wmapped + morse[ord(c) - ord('a')]
        if not wmapped in wordsmapped:
            wordsmapped.append(wmapped)
    return len(wordsmapped)
print(uniqueMorseRepresentations(words))

Clever ways

The brute force method works. Now we try to find improvements.

1. Can we loop through once instead of double loop?