Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction 
2.
Problem Statement
2.1.
Example
3.
Solution Using Trie Data Structure
3.1.
C++ Implementation
3.1.1.
Input
3.1.2.
Output
3.2.
Complexity
3.2.1.
Time complexity 
3.2.2.
Space complexity 
4.
FAQs
5.
Key Takeaways
Last Updated: Mar 27, 2024

Decode Morse Code

Author Teesha Goyal
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction 

Morse code is the most common binary code for radio communication. Morse code is a sequence of dots (.) and dashes (-) characters that can be deciphered using a mapping to get the desired decoded message. We are given a morse code in this problem and need to find the number of phrases formed when the code is deciphered. 

Problem Statement

In this problem, a string is taken as an input containing the morse code, which must be deciphered. The string only consists of dots and dashes and not whitespaces, so different words can be formed when taking the different number of characters at a time, leading to different phrases. We need to find the total number of such phrases formed using the complete string.

Following is the mapping of morse code to English alphabets.

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


There is d number of cases given, and for each case, a string of morse code and a dictionary of appropriate words is given to form the phrases. Each dictionary word is a sequence of at most 20 capital letters. 

The first line of input is an integer d, the number of samples or input strings followed by d lines of strings, where d can be from 1 to 20. The following line consists of an integer n that gives the number of words in the dictionary followed by n lines containing one word.

The output consists of exactly d lines where each line gives the output for corresponding input that is an integer, the number of different phrases that can be deciphered from the given string.

Example

Input

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


Output

2


Explanation

Here, the two phrases that can be deciphered from the complete given morse code are AT TACK AT DAWN and ATTACK AT DAWN. None of the other phrases is possible for the given morse code sequence and dictionary of words hence the answer 2.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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;
}


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!

Previous article
Inappropriate Words Filter
Next article
Prefix-Suffix Palindrome
Live masterclass