pipipzz's blog

SPOJ MORSE
By pipipzz, 10 years ago, In English

I was reading "Using Tries" on topcoder and so tried to solve MORSE I think it requires Trie and DP. I have implemented a trie but I have not figured out the DP for this case. Can someone please explain me the DP approach ? Thanks.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it 
int D(int pos, int trieNode) {
    if (s.size() == pos)
       return isValidWord(trieNode) ? : 1 : 0;
    int &res = dp[pos][trieNode];
    if (res != -1)
        return res;
    res = 0;
    for (int i = 0; i < 26; ++i)
       if (pos + morse[i].size() <= s.size() && s.substr(pos, morse[i].size()) == morse[i]) {
           int nextTrieNode = NextTrieNodeByLetter(trieNode, i);
           if (nextTrieNode != -1) 
              res += D(pos + morse[i].size(), nextTrieNode);
       } 
    return res;
}
→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    also, before return res; there should be if (isValidWord(trieNode) res += D(pos, rootNode);

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

@Alias: could you please tell me what does NextTrieNodeByLetter() return? if you could explain the approach it would be very helpful

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    NextTrieNodeByLetter() returns -1 if node trieNode has no edge marked with letter i or corresponding next node. It makes a try to go from node trieNode using letter i. I do not know what else I can say.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      morse[] — array of morse strings. A trie is builded from dictionary words.

      → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In my solution dp[i] was number of ways that we can translate an string starting from i-th place of morse string to end of it.

→ Reply