Advertisement
alex0sunny

cheet

Dec 19th, 2021
179
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.49 KB | None | 0 0
  1. def cheet(text, words):
  2.     max_len = max([len(word) for word in words])
  3.     dp = [True] + [False] * len(text)
  4.     for i in range(1, len(text)+1):
  5.         for j in range(1, min(max_len+1, i+1)):
  6.             if dp[i-j]:
  7.                 suffix = text[i-j:i]
  8.                 if suffix in words:
  9.                     dp[i] = True
  10.                     break
  11.     return dp[-1]
  12.  
  13.  
  14. text = input()
  15. n = int(input())
  16. words = set([input() for _ in range(n)])
  17. print('YES' if cheet(text, words) else 'NO')
  18.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement