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

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

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
  • Проголосовать: не нравится

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

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

→ Ответить
»
12 лет назад, скрыть # |
 
Проголосовать: нравится 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.

→ Ответить