Decode Morse Code

Solution Using Trie Data Structure

The solution to the problem is to use a trie data structure to efficiently search for the words from the given dictionary. First of all, a trie dicttree is created for all the words in the dictionary, then another array state is created, which holds all the possible letters for index i that can be deciphered from the position i in the given morse code. Then, words are decoded using both the state and the dicttree array by depth-first search.

The steps of implementation are:

• Declare important variables morsecode, dict, dicttree, state, dp, N, size, dollar and pattern globally, so there is no need to pass them to each function explicitly
   
• Take in the input 
   
• Call build_dict_tree function to build the trie structure for all the words in the dictionary.
   
• In the build_dict_tree function, first, we initialise the dicttree with 0 value. Next, loop over for each word in the dictionary. Set cursor to 0 and temp to 0. While dicttree[cursor][dict[i][temp] - ‘A’] is not equal to 0 update cursor and increment temp. Break when temp becomes greater than or equal to the size of the current word. If the temp is equal to the size of the word, increment dicttree[cursor][dollar] by 1. Otherwise, use a while loop until temp is less than the size of the word and update the value of dicttree[cursor][dict[i][temp - ‘A’] by count. Assign count to the cursor. Increment count and temp. After the loop ends, increment dicttree[cursor][dollar] by 1.
   
• Call the build_state function to create a state function that holds the letters that can be decoded for each position in morsecode.
   
• In the build_state function, firstly clear the state array. Implement a for loop to traverse over the morsecode, and inside it, implement another for loop for each letter in the pattern. Set var to True. Implement a for loop to check whether the sequence for each character from the pattern can be decoded at index i for morsecode or not. If a letter can be formed, store it in the state array. 
   
• Initialise the dp array, which is used to form the words.
   
• Call dfs function to form the words and find the number of phrases. The function takes three arguments - u, start and trie, all integers.
   
• In the dfs function, If u is equal to size then return dicttree[trie][dollar]. If start is equal to u and dp[u] is not equal to -1 return dp[u]. Initialize variable answer to 0. Implement a for the position u in morsecode and traverse for its size, store state[u][i] in c. if dicttree[trie][c] is not equal to 0, call dfs function recursively with u+ size of pattern[c], start and dicttree[trie][c] and add the return value to answer.
   
• If dicttree[trie][dollar] is not equal to 0, add 1LL times dicttree[trie][dollar] times dfs(u,u,0) to answer. Finally, check if start is equal to u. If equal, update dp[u] with answer and return answer
   
• Store the return value of the dfs function in answer and print answer.

C++ Implementation

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#include <cassert>
using namespace std;

// Defining some important variables globally so that all the function can use them without being passed explicitly
string morsecode;
vector<string> dict;
int dicttree[200003][30];
vector<int> state[100003];
long long dp[100003];
int N, size;
int dollar = 29;
string pattern[26] = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};

//build_dict_tree is a function that is used to construct the trie data structure for dictionary of words
void build_dict_tree(){

    //intiializing dicttree
    for(int i=0;i<=200000;++i){
        for(int j=0;j<30;++j){
            dicttree[i][j] = 0;
        }
    }

    int count = 1;
    //For each word in the dictionary
    for(int i=0;i<N;++i){
        int cursor = 0;
        int temp = 0;
        //move forward till the point that is present in the trie
        while(dicttree[cursor][dict[i][temp]-'A'] != 0){
            cursor = dicttree[cursor][dict[i][temp]-'A'];
            ++temp;
            //break when temp reaches the length of the word
            if(temp>= dict[i].size())break;
        }

        if(temp== dict[i].size()){
            dicttree[cursor][dollar] += 1;
        } else {
            //add the letters of the words which are not added yet
            while(temp < dict[i].size()){
                dicttree[cursor][dict[i][temp]-'A'] = count;
                cursor = count;
                ++count;
                ++temp;
            }
            dicttree[cursor][dollar] += 1;
        }
    }
}

void build_state(){
    //For the length of the morsecode, create an empty state array
    for(int i=0;i<size;++i){
        state[i].clear();
    }
    //state array holds the letters that can be formed on that position of the morsecode
    for(int i=0;i<size;++i){
        //for each letter in pattern
        for(int j=0;j<26;++j){
            bool var = true;
            for(int k=0;k<pattern[j].size();++k){
                if(morsecode[i+k] != pattern[j][k]){
                    var = false;
                    break;
                }
            }
            //adding the letter to the list if its pattern is present at i index in morsecode
            if(var) state[i].push_back(j);
        }
    }
}

//using Depth first search approach to form words and find the number of different phrases that can be formed
long long dfs(int u, int start, int trie){
    assert(u<=size);
    if(u == size){
        return dicttree[trie][dollar];
    }
    if(start == u) if(dp[u]!=-1)return dp[u];
    //initialize a variable to store the number of phrases with complete morsecode
    long long answer= 0;
    for(int i=0;i<state[u].size();++i){
        int c = state[u][i];
        if(dicttree[trie][c])answer += dfs(u+pattern[c].size(), start, dicttree[trie][c]);
    }
    if(dicttree[trie][dollar]){
        answer += 1LL*dicttree[trie][dollar] * dfs(u, u, 0);
    }
    if(start == u) {
        dp[u] = answer;
    }
    return answer;
}

int main(){
    //taking in number of test cases
    int num_of_test_cases;
    scanf("%d",&num_of_test_cases);

    //for each test case
    while(num_of_test_cases--)
    {
        //input the morse cose
        cin >> morsecode;
        size = morsecode.size();

        //input the number of words
        scanf("%d",&N);
        dict = vector<string>(N+3);

        //input the words of the dictionary
        for(int i=0;i<N;++i){
            cin >> dict[i];
        }

        //build trie for the words in the dictionary
        build_dict_tree();
        build_state();

        //initializing the dp array
        for(int i=0;i<size;++i){
            dp[i] = -1;
        }
       
        long long answer = dfs(0,0,0);
        cout << answer << endl;
    }
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Input

1 
.---.--.-.-.-.---...-.---. 
6 
TICK
TACK 
DUSK
DAWN
ATTACK 
AT

Output

2

Complexity

Time complexity 

O(N*M), where N is the length of the morsecode and M is the sum of the length of the dictionary words.

Reason: Since we are traversing over all the positions and then checking for the word in the trie structure hence the complexity of O(NM).

Space complexity 

O(N+W), where N is the length of the morsecode and W is the number of words in the dictionary.

Reason: For each test case, we are using the same variables; the complexity is equal to the length of the largest input string, the morse code or the number of words.

FAQs

1. What is Trie?
   Trie is a data structure that is used to store and locate key values from a given set. It is also known as prefix tree or digital tree. A graph can be used to visualise the trie data structure.
    
2. What is Morse Code?
   Morse code is the encoding primarily used in telecommunication where the characters are encoded as a sequence of two different signal pulses denoted by dots and dashes.
    
3. What is DFS?
   Depth-First Search(DFS) is a traversal or searching algorithm for trees and graphs which uses a stack to remember the next node to traverse/search.
    
4. How do you analyse the performance of an algorithm?
   The performance of an algorithm is analysed using Time and Space complexity. Time complexity gives the run time an algorithm, and space complexity gives the amount of space the algorithm takes when executed. 
    
5. What is dynamic programming?
   Dynamic programming is a programming technique used to optimise the solution of problems by remembering the solutions to the subproblems that occur repeatedly and again, hence avoiding solving the same subproblem repeatedly. 

Key Takeaways

In this article, we learned how to solve the problem of "Decode Morse Code”. To solve this problem, we used the Trie data structure. Trie is a data structure that helps efficiently search the keywords in a set of words.

Also check out - Data Dictionary In Software Engineering

Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more? 
Attempt our Online Mock Test Series on Coding Ninjas Studio now!

Happy Coding!