Блог пользователя pipipzz

SPOJ MORSE
Автор pipipzz, 10 лет назад, По-английски

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.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
10 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится 
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;
}
→ Ответить
»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить