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

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.

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.

What is DFS?
DepthFirst Search(DFS) is a traversal or searching algorithm for trees and graphs which uses a stack to remember the next node to traverse/search.

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.

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 productbased companies like Amazon, Google, Microsoft, and more?
Attempt our Online Mock Test Series on Coding Ninjas Studio now!
Happy Coding!