rahul_1234's blog

Trie
By rahul_1234, history, 8 years ago, In English

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?

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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.

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

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.

→ Reply