Se citesc un sir S si un dictionar cu n cuvinte. Verificati, folosind Programarea Dinamica, daca sirul S poate fi impartit intr-o secventa de unul sau mai multe cuvinte din dictionar (un cuvant poate fi folosit de oricate ori).
- Date de intrare
- Pe prima linie se citeste sirul S. Pe a doua linie se citeste n. Pe a treia linie se citesc cele n cuvinte ale dictionarului.
- Date de iesire
- Se afiseaza DA daca S poate fi impartit in cuvinte din dictionar, respectiv NU in caz contrar.
- Restrictii
- 1 <= lungimea S <= 1000, 1 <= n <= 1000, 1 <= lungimea unui cuvant <= 20
Exemple
Exemplul 1
Intrare
leetcode 2 leet code
Iesire
DA
Exemplul 2
Intrare
applepenapple 2 apple pen
Iesire
DA