Tách Từ Thành Câu

Buổi 21 — DP 1D cổ điển Dynamic Programming dynamic-programming
Points
26
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề 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 YES nếu có thể tách được, ngược lại in ra NO.
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$
Draft saved