Tách Từ Thành Câu
Points
26
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Đề bài
Cho một chuỗi $S$ độ dài $N$ chỉ gồm các chữ cái Latinh thường và một từ điển gồm $M$ từ. Hãy kiểm tra xem chuỗi $S$ có thể tách thành một dãy liên tiếp các từ đều nằm trong từ điển hay không (mỗi từ trong từ điển có thể được dùng nhiều lần).
Cấu trúc con tối ưu: $dp[i] = \text{true}$ nếu tiền tố độ dài $i$ tách được, khi tồn tại $j < i$ sao cho $dp[j] = \text{true}$ và xâu con $S[j..i-1]$ nằm trong từ điển.
Dữ liệu vào
- Dòng đầu chứa chuỗi $S$ ($1 \le |S| \le 2000$).
- Dòng thứ hai chứa số nguyên $M$ ($1 \le M \le 1000$).
- Dòng thứ ba chứa $M$ từ trong từ điển cách nhau bởi dấu cách (mỗi từ có độ dài từ $1$ đến $50$).
Dữ liệu ra
- In ra
YESnếu có thể tách được, ngược lại in raNO.
Ví dụ
| Input | Output |
|---|---|
| leetcode\n2\nleet code | YES |
| catsandog\n5\ncats dog sand and cat | NO |
Giới hạn
- $1 \le |S| \le 2000$
- $1 \le M \le 1000$
Community Discussion