Đề bài
Decide whether text can be split into a sequence of words from words. Words may be reused. Dynamic programming over prefixes solves it efficiently.
Implement can_break(text, words).
Input
text: Lowercase letters only. words: The dictionary; each word has 1–50 lowercase letters.
Output
Return true if a split exists.
Ràng buộc
0 ≤ length of text ≤ 5,000; 1 ≤ words ≤ 1,000
Ví dụ
Đầu vào:
text = "applepenapple"
words = ["apple", "pen"]
Kết quả mong đợi:
expected = TrueĐầu vào:
std::string text = "applepenapple";
std::vector<std::string> words = {"apple", "pen"};
Kết quả mong đợi:
bool expected = true;Đầu vào:
string text = "applepenapple";
string[] words = new string[] {"apple", "pen"};
Kết quả mong đợi:
bool expected = true;Giải thích
"apple" + "pen" + "apple", reusing "apple".
Đầu vào:
text = "catsandog"
words = ["cats", "dog", "sand", "and", "cat"]
Kết quả mong đợi:
expected = FalseĐầu vào:
std::string text = "catsandog";
std::vector<std::string> words = {"cats", "dog", "sand", "and", "cat"};
Kết quả mong đợi:
bool expected = false;Đầu vào:
string text = "catsandog";
string[] words = new string[] {"cats", "dog", "sand", "and", "cat"};
Kết quả mong đợi:
bool expected = false;Giải thích
Every split leaves "og" or "ando" unmatched: false.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Một tiền tố được xem là tách được nếu có một vị trí tách trước đó có thể nối tới nó bằng một từ trong từ điển.
Gợi ý 2
Quy hoạch động theo vị trí hoạt động tốt khi bạn kiểm tra độ dài từ hoặc khớp từ điển hiệu quả.
Gợi ý 3
Chuỗi rỗng là tách được ngay, nhưng việc dùng lại từ nhiều lần vẫn phải được cho phép trong suốt quá trình duyệt.
Độ phức tạp mong đợi
thời gian O(n^2), bộ nhớ phụ O(n)
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.