Word Break
Bạn nhận được một chuỗi s và một danh sách từ wordDict. Trả về true nếu bạn có thể chia s thành các phần mà tất cả đều là từ trong wordDict, nếu không thì trả về false.
Các phần giữ nguyên thứ tự và ghép lại sử dụng mỗi ký tự của s đúng một lần. Bạn có thể dùng một từ bao nhiêu lần tùy ý, và không cần dùng hết mọi từ.
Hàm
- sstring
- chuỗi cần tách thành các từ
- wordDictstring-array
- các từ bạn có thể dùng, mỗi từ bao nhiêu lần tùy thích
- Trả vềboolean
- true nếu s có thể được tách thành các từ trong từ điển, false nếu không
Ràng buộc
1 ≤ s.length ≤ 3001 ≤ wordDict.length ≤ 10001 ≤ wordDict[i].length ≤ 20svà mỗi từ chỉ chứa các chữ cái tiếng Anh viết thường.- Các từ trong
wordDictđều khác nhau.
Ví dụ
- Đầu vào
- s = "sunflowerseed"wordDict = ["sun", "flow", "flower", "seed"]
- Đầu ra
- true
- Giải thích
- Hãy cắt thành
sun,flower,seed. Lấyflowsausunsẽ còn lạier, nhưng không có từ nào bắt đầu bằng phần này, nên từ đầu tiên phù hợp không phải lúc nào cũng là từ đúng.
- Đầu vào
- s = "bananaban"wordDict = ["ban", "ana"]
- Đầu ra
- true
- Giải thích
ban+ana+banbao phủ chuỗi và sử dụngbanhai lần, điều này được phép.
- Đầu vào
- s = "pineappletart"wordDict = ["pine", "apple", "pineapple", "tar"]
- Đầu ra
- false
- Giải thích
- Cả
pine+applevàpineappleđều để lạitart. Chỉtarvừa chỗ đó, nhưng lại còn thừa mộtt, nên không có cách cắt nào phù hợp.
Câu hỏi mở rộng
Trả về số từ ít nhất mà một phép cắt hợp lệ có thể dùng, hoặc -1 nếu không thể cắt s. Bảng thay đổi như thế nào, và thời gian chạy có thay đổi không?
Gợi ý
Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.
Từ đầu tiên của mỗi lượt cắt là một từ bắt đầu bằng
s. Sau khi chọn từ đó, bạn còn câu hỏi nào?Việc có thể cắt các chữ cái từ một chỉ số nào đó đến cuối hay không chỉ phụ thuộc vào chỉ số đó. Chỉ có
n + 1câu hỏi như vậy, nên hãy ghi nhớ từng câu trả lời, nhất là những câu trả lờifalseở trên.Gọi
canEnd[i]cho biết liệu có thể cắt bỏichữ cái đầu tiên hay không, vớicanEnd[0] = true. Khi đó,canEnd[end]là true nếu có mộtcanEnd[start]là true và các chữ cái từstartđếnendtạo thành một từ. Lưu các từ trong một tập hợp băm và chỉ thử những đoạn không dài hơn từ dài nhất.
Lời giải
Chỉ ghép từng từ một thì không hiệu quả, còn thử mọi cách cắt thì cần thời gian theo cấp số nhân. Nhưng việc phần còn lại của s có thể được chia hay không chỉ phụ thuộc vào vị trí bắt đầu, nên chỉ có n + 1 câu hỏi. Trong phần dưới đây, n là độ dài của s, m là số từ và L là độ dài của từ dài nhất.
Thử từng từ ở mọi vị trí
Đúng, nhưng không chạy xong với các test lớn nhất
Ý tưởng
Mảnh đầu tiên phải là một từ mà s bắt đầu bằng. Hãy thử từng từ như vậy rồi đặt cùng một câu hỏi về các chữ cái còn lại; nếu phần còn lại rỗng thì mọi chữ cái đều được tách hết. Thử mọi từ đầu tiên rồi đến mọi từ thứ hai sẽ không bỏ sót cách tách hợp lệ nào.
Cách này kiểm tra đi kiểm tra lại cùng một phần còn lại. Với 299 chữ a liên tiếp rồi đến một chữ b, và các từ a, aa cho đến mười chữ a, có hơn 10^89 cách chia các chữ a thành từng khối để đến chữ b rồi thất bại, và đệ quy thử tất cả các cách đó.
Thuật toán
- Viết
canSplit(start): các chữ cái từstartđến cuối có thể được tách ra không? Nếustartbằng độ dài củas, hãy trả vềtrue. - Với mỗi từ mà
schứa tại chỉ sốstart, nếucanSplit(start + its length)làtrue, hãy trả vềtrue. - Nếu không, hãy trả về
false. Đáp án làcanSplit(0).
def wordBreak(s, wordDict):
def can_split(start):
# Can s[start:] be cut into dictionary words?
if start == len(s):
return True # nothing left to cut
for word in wordDict:
if s.startswith(word, start) and can_split(start + len(word)):
return True
return False
return can_split(0)Đệ quy với bộ nhớ đệm
Ý tưởng
Đáp án cho phần dư chỉ phụ thuộc vào start, có n + 1 giá trị. Trong ví dụ với chữ a, phần dư tại chỉ số 20 đạt được sau hai khối mười, sau hai mươi chữ a đơn lẻ và theo vô số cách khác, và lần nào cũng là false. Hãy lưu đáp án cho mỗi giá trị start một lần rồi dùng lại.
Bộ nhớ đệm phải giữ lại các đáp án false. Một đáp án true kết thúc toàn bộ quá trình tìm kiếm ngay lập tức, vì vậy mọi công việc lặp lại đều nằm trong các nhánh không thành công.
Mỗi giá trị start thử mọi từ, so sánh tối đa L chữ cái: thời gian O(n × m × L), tối đa 6 × 10^6 lần kiểm tra chữ cái và bộ nhớ O(n).
Thuật toán
- Tạo một bảng ghi nhớ có một ô cho mỗi chỉ số, ban đầu đánh dấu từng ô là chưa tính.
- Trong
canSplit(start), trả vềtruekhi đến cuốis, hoặc trả về đáp án đã lưu nếu ô đó đã có giá trị. - Nếu không, hãy thử từng từ như trong cách đệ quy thông thường, lưu kết quả vào ô đó, kể cả
false, rồi trả về kết quả.
def wordBreak(s, wordDict):
memo = [None] * len(s) # memo[start]: answer for s[start:], None until worked out
def can_split(start):
if start == len(s):
return True
if memo[start] is not None:
return memo[start]
result = False
for word in wordDict:
if s.startswith(word, start) and can_split(start + len(word)):
result = True
break
memo[start] = result
return result
return can_split(0)Duyệt từ dưới lên qua các tiền tố bằng tập hợp băm
Ý tưởng
Xử lý các tiền tố. Gọi canEnd[i] cho biết liệu có thể tách i chữ cái đầu tiên hay không; canEnd[0] là true, vì tiền tố rỗng không cần từ nào. Có thể tách đúng end chữ cái đầu tiên khi mảnh cuối, từ start đến end, là một từ và canEnd[start] là true. Khi điền từ trái sang phải, mọi canEnd[start] bạn cần đều đã có giá trị.
Đưa các từ vào một tập hợp băm. Không từ nào dài hơn L, nên chỉ có thể khớp với L mảnh kết thúc tại end, bất kể từ điển lớn đến đâu. Với sunflowerseed, canEnd là true tại 0, 3, 7, 9 và 13; ngõ cụt tại 7 không gây hại.
Mỗi trong số n vị trí tra cứu tối đa L mảnh, mỗi mảnh tốn đến L bước để tạo và băm: O(n × L²), tối đa 1.2 × 10^5 bước, cộng thêm O(m × L) cho tập hợp.
Thuật toán
- Đưa các từ vào một tập hợp băm; ghi nhận độ dài lớn nhất
L. - Tạo
canEndvớin + 1phần tử, tất cả đều làfalse, rồi đặtcanEnd[0]thànhtrue. - Với mỗi
endtừ 1 đếnnvà mỗilengthtừ 1 đếnmin(L, end): nếucanEnd[end-length]làtruevà phần có độ dài đó kết thúc tạiendnằm trong tập hợp, đặtcanEnd[end]thànhtruerồi dừng. - Trả về
canEnd[n].
def wordBreak(s, wordDict):
words = set(wordDict)
longest = max(len(word) for word in wordDict)
n = len(s)
# can_end[i]: the first i letters split into dictionary words
can_end = [False] * (n + 1)
can_end[0] = True # the empty prefix needs no words
for end in range(1, n + 1):
# The last word is s[end-length:end], and no word is longer than longest.
for length in range(1, min(longest, end) + 1):
if can_end[end - length] and s[end - length:end] in words:
can_end[end] = True
break
return can_end[n]
Lỗi thường gặp và trường hợp biên
- Cắt theo cách tham lam. Cắt từ dài nhất trước sẽ tách
carpetalthànhcarpetvà bỏ lạial, dùcar+petalvẫn ghép được; cắt từ ngắn nhất trước sẽ mắc kẹt vớisunflowerseed. - Chỉ lưu các câu trả lời
truevào bộ nhớ đệm. Công việc lặp lại nằm ở các nhánhfalse, vì vậy ví dụ với các chữ a vẫn có độ phức tạp hàm mũ. - Tạo bảng thiếu một mục.
canEndcầnn + 1mục, ứng với độ dài tiền tố từ 0 đếnn. - So sánh vượt quá cuối của
s, chẳng hạn như so sánh từabcvới phần còn lại làab. Hãy kiểm tra độ dài trước. - Trong Lua và R, vị trí trong chuỗi bắt đầu từ 1: một đoạn có độ dài
kkết thúc ở chữ cáiesẽ bắt đầu tạie-k+1.
Câu hỏi thường gặp3
Độ phức tạp thời gian của Word Break là gì?
Bảng bottom-up dùng tập hợp băm có độ phức tạp O(m × L + n × L²), trong đó n là độ dài của s, m là số từ và L là độ dài của từ dài nhất. Việc so sánh từng từ tại mọi vị trí có độ phức tạp O(n × m × L). Đệ quy thuần túy có độ phức tạp theo hàm mũ.
Word Break là bài toán quy hoạch động hay bài toán đồ thị?
Cả hai. Theo quy hoạch động, canEnd[i] cho biết liệu có thể tách i chữ cái đầu tiên hay không. Theo cách biểu diễn bằng đồ thị, mỗi chỉ số là một nút, với một cạnh từ i đến j khi các chữ cái ở giữa tạo thành một từ, và bạn cần xác định liệu có thể đi từ 0 đến n hay không. Tìm kiếm theo chiều rộng thực hiện công việc tương tự như bảng.
Làm thế nào để liệt kê mọi câu thay vì trả về giá trị đúng hoặc sai?
Quay lui: tại mỗi chỉ số, thử mọi từ phù hợp, đệ quy trên phần còn lại và ghi nhớ danh sách câu cho từng chỉ số. Trước tiên, chạy bảng đúng hoặc sai để bỏ qua việc tìm kiếm với chuỗi không thể phân tách. Số lượng câu có thể tăng theo cấp số nhân, vì vậy kích thước đầu ra quyết định thời gian chạy.
Bài tập tương tự
Các bài tập dùng cùng ý tưởng. Giải hai hoặc ba bài là bạn sẽ nhớ được mẫu này.
def wordBreak(s, wordDict):
# Viết code ở đâyKiểm thử #1
Kiểm thử #2
Kiểm thử #3
Đối số
s = "sunflowerseed" wordDict = ["sun", "flow", "flower", "seed"]
Đầu ra mong đợi
true