Unique Morse Code Words

Question

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:

[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--",
 "-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]

Now, given a list of words, each word can be written as a concatenation of the Morse code of each letter. For example, "cba" can be written as "-.-..--...", (which is the concatenation "-.-." + "-..." + ".-"). We’ll call such a concatenation, the transformation of a word.

Return the number of different transformations among all words we have.

Example:

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

Note:

  • The length of words will be at most 100.
  • Each words[i] will have length in range [1, 12].
  • words[i] will only consist of lowercase letters.

See on Leetcode

Solution

class Solution {
    public int uniqueMorseRepresentations(String[] words) {

        char[] alphabetArr = {
            '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'
        };
        String[] morseCodeArr = {
            ".-",
            "-...",
            "-.-.",
            "-..",
            ".",
            "..-.",
            "--.",
            "....",
            "..",
            ".---",
            "-.-",
            ".-..",
            "--",
            "-.",
            "---",
            ".--.",
            "--.-",
            ".-.",
            "...",
            "-",
            "..-",
            "...-",
            ".--",
            "-..-",
            "-.--",
            "--.."
        };
        Map < Character, String > morseMap = new HashMap < > ();
        Set < String > morseRepresentation = new HashSet < > ();
        boolean addMorseWord = true;

//map the alphabet and their unique morse code word.
        for (int i = 0; i < morseCodeArr.length; i++) {

            morseMap.put(alphabetArr[i], morseCodeArr[i]);

        }
        /* loop through each word in the word array, then convert each word into
           morse code word  and add to the Morse representation set.
        */
        for (int i = 0; i < words.length; i++) {

            StringBuffer morseCodeWord = new StringBuffer();

            char[] wordCharArr = words[i].toCharArray();

            for (int j = 0; j < wordCharArr.length; j++) {

                if (morseMap.containsKey(wordCharArr[j])) {

                    morseCodeWord.append(morseMap.get(wordCharArr[j]));

                } else {
                    /* if there is bad data in the word as input, the word will
                       not be considered. addMorseWord flag does this job. */
                    addMorseWord = false;
                    break;
                }


            }
            if (addMorseWord) {
                morseRepresentation.add(morseCodeWord.toString());
            }
            addMorseWord = true;

        }
        /* return the size of the morse representation set as it has the unique
           set of morse code words possible from the input word array
        */
        return morseRepresentation.size();

    }
}

Test Cases

  • A word array with duplicate words as input. for eg. [“doe”, “doe”, “doe”, “hello”].
  • A word array with no duplicate words as input. for eg. [“abc”, “doe”, “xxx”, “hello”].
  • A word array with maximum allowed number of words as input and each word has maximum length of 12 and no duplicate words exist in the array (100 in this case).
  • A word array whose words corresponding morse codes are same to other words morse code for eg. [“gin”, “zen”, “gig”, “msg”]
  • Although not handled by the above program, the below tests would fail. But when testing for production code, these should fail with appropriate error message (negative testing).
    • Uppercase alphabets in the input array for eg. [“DOE”, “DoE”, “doe”, “DOE”].
    • A word array with morse code as input for eg. [“–…-.”, “–…–”, “–…-.”, “–…–”].
    • A word array with UTF-8 characters and special characters similar to morse code within words for eg. [“do好e”, “do-..e”, “do好e”, “do-..e”, “hello”].
  • Input word array as empty or null (not handled by code above, but should be tested).

See also