Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

Блог пользователя 123virat.sharma

Genral problem

Автор 123virat.sharma, 10 лет назад, По-английски

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

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

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

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).

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

    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 :)

    → Ответить