Count distinct strings possible by replacing each character by its Morse code

Given an array of strings arr[], the task is to count the number of distinct strings that can be generated from the given array by replacing each character of the strings by its Morse code. Below is the Morse code of all the lowercase alphabets:

Examples:

Input: arr[] = {“gig”, “zeg”, “gin”, “msn”}
Output: 2
Explanation: 
Replacing each character of the strings of the given array to its Morse code: 
gig = “–…–.” 
zeg = “–…–.” 
gin = “–…-.” 
msn = “–…-.” 
Morse code of the strings “gig” and “zeg” are equal. 
Morse code of the strings “gin” and “msn” are equal. 
Therefore, the total count of distinct elements of the given string by replacing the characters to its Morse code is equal to 2. 
 

Input: arr[] = {“neveropen”, “for”, “neveropen”}
Output: 2

Approach 1: Follow the steps below to solve the problem:

• Initialize an array, say morseCode[] to store the Morse code of all lowercase characters.
• Create a set, say st to store distinct elements of the array by replacing each character to its Morse code.
• Traverse the array and insert the Morse code of the string of the array into st.
• Finally, print the count of elements present in st.

Below is the implementation of the above approach.

2

Time Complexity: O(N×M), where N is the size of the array and M is the length of a word.
Auxiliary Space: O(N)

Approach 2: Using python dictionary

Algorithm:

• Create a dictionary that map value of English alphabet to Morse.
• Use lambda function to loop through every character.
• Use Counter to count unique element after each word is converted to its corresponding morse. 

2

Time Complexity: O(N), where N is the size of the array
Auxiliary Space: O(N)