Advertisement
viligen

longest_string_chain_DP

Aug 10th, 2022
749
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.78 KB | None | 0 0
  1. from collections import deque
  2.  
  3. words = input().split()
  4.  
  5. size = [0] * len(words)
  6. prev = [None] * len(words)
  7.  
  8. best_size = 0
  9. best_idx = 0
  10.  
  11. for idx in range(len(words)):
  12.     current_word = words[idx]
  13.     current_size = 1
  14.     parent = None
  15.     for prev_idx in range(idx - 1, -1, -1):
  16.         prev_word = words[prev_idx]
  17.         if len(prev_word) >= len(current_word):
  18.             continue
  19.         if size[prev_idx] + 1 >= current_size:
  20.             current_size = size[prev_idx] + 1
  21.             parent = prev_idx
  22.     size[idx] = current_size
  23.     prev[idx] = parent
  24.  
  25.     if current_size > best_size:
  26.         best_size = current_size
  27.         best_idx = idx
  28.  
  29. lis = deque()
  30. idx = best_idx
  31.  
  32. while idx is not None:
  33.     lis.appendleft(words[idx])
  34.     idx = prev[idx]
  35.  
  36. print(*lis)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement