123virat.sharma's blog

Genral problem

By 123virat.sharma, 10 years ago, In English

hey can anybody tell me good algorithm for finding longest list of words with matching start and end letters
example -> acrush humblefool lilo tourist then longest list will be acrush humblefool lilo

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

»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I suppose the words can't repeat.

If you can change the order of words (from what you're given on the input), then it's NP-complete, because you need to find a Hamiltonian path. In that case, I guess it'd be DP by (current word, subset of words used so far).

If you can only pick a subsequence of given words, then it's simple DP by (words up the i-th processed so far, max. number of words possible if the last one ends with character c).

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

    Ooh Sry for sort of information and my bad english and yes words can't repeat & we can change the order of words. thnx to suggest me. bt if there words are 10000 then we can't use bitmasking(I think) so is there another algorithm :)

    → Reply