SPOJ MORSE - Decoding Morse Sequences

Problem Statement:
SPOJ - MORSE

Solution:
This is a very... tedious problem. The idea is to build a trie structure for efficient search of words in the given dictionary. Since each letters in the dictionary is at most only 20 letters long, which can contain up to 26 letters, we can build the trie structure in O(M) time where M is the total sum of the lengths of the words.

Next, we do a depth first search like algorithm on the morse code (defined as morse[i]), starting from i = 0. Initially we also have a pointer cur pointing to the root of the trie. So the states of the algorithm is S(i, cur), where S(i,cur) gives us the number of ways to match morse[i..N] with words from dictionary.