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

Trie
Автор rahul_1234, история, 8 лет назад, По-английски

Giving a string and an string dictionary, find the longest string in dictionary which can formed by deleting some characters of the giving string.

Example:

S = abpcplea,

Dict = {ale, apple, monkey, plea},

the return "apple"

Can somebody provide trie solution( O(N*K) ), N: length of string, K: length of longest word?

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

»
8 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

This can be solved using DP.

The state is: (node, ind), representing the current trie node, and the current index in the given word, respectively.

The transitions are:

  • Delete the current index, then you go to (node, ind + 1)
  • Keep the current index, which adds 1 to the answer, then you go to (child, ind + 1), where child is the node's child corresponding to the character at ind.

Of course, the base case is when you reach a leaf or the end of the string.

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

I think at least we have to check all words in dictionary, so if L = length of dictionary, we can solve in O(N * L).

You can check if one string is other's substring in O(N) (see here), so check all words in dictionary and return longest one.

→ Ответить