Unique Morse Code Words.

Greetings, It's day #12 of my coding diary.

Problem of the day - Unique Morse Code Words

Tag - Easy

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.

As, I saw the problem, my mind started drawing pictures of iterating over each word from the given words list to calculate it's morse code. To remember the output morse code, I will put it in hashmap so that next time when I calculate the morse code for next word, I can know if it is already generated or not. And, that would be my number of different transformations.

Pretty easy peasy! Easy tag does the justice with this problem. It should not take more than 5 minute to code it.

Here is my ugly code

class Solution {
public:
    int uniqueMorseRepresentations(vector<string>& words) {
        string list[26] = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
        map<string,int> hash;
        string code = "";
        int res = 0;
        for(auto word: words) {
            code = "";
            for(char c: word) {
                code += list[c - 'a'];
            }
            if(hash[code] == 0) res++;
            hash[code]++;
        }
        return res;
    }
};

Oops! I copied the morse code list from the question itself.

A simple explanation of my tiny algorithm

Maintain a list of morse code for each alphabet
iterate over the list of words
for each word, for each charactor, find morse code from the list and calculate the final morse code by concatenation of morse code of each letter
Check if we already got this morse code, if no, increase the result count
Set value in hashmap for this morse code
Return the result count at the end.

That was the easiest way, I could explain my approach.

In order to find some optimized approach then mine, I checked out discussion & solution tab. It seems that's the optimized one.

Some smart folks have used unordered set instead of hash map. As set makes all values unique, output would be the total unique values.

You might like previous editions of my coding diary