Tách từ
Bài học 14 trên 14 trong khóa học Cây tiền tố, chuỗi cấu trúc dữ liệu số 8 của Coddy.
Cho một chuỗi s và một từ điển gồm các từ, liệu ta có thể tách s thành một chuỗi các từ trong từ điển mà không còn ký tự nào không? Có thể tách "leetcode" thành "leet" + "code" nếu cả hai từ đều có trong từ điển; còn "catsandog" thì không thể tách, dù chia theo cách nào.
Một lượt quy hoạch động sẽ giải quyết được bài toán. Định nghĩa dp[i] là có thể tách i ký tự đầu tiên thành các từ không? Bắt đầu với dp[0] = true. Với mỗi i sao cho dp[i] là true, duyệt trie từ vị trí i trong chuỗi; mỗi khi lượt duyệt đến một nút isEndOfWord tại chỉ số j, đặt dp[j+1] = true.
Trie giúp mỗi lượt duyệt diễn ra nhanh: chỉ cần thiếu một ký tự là lượt duyệt kết thúc. Đáp án cuối cùng nằm trong dp[n].
Thử thách
Trung bìnhViết một hàm wordBreak nhận một chuỗi s và một mảng chuỗi dictionary, rồi trả về true nếu có thể tách s thành một hoặc nhiều phần không chứa khoảng trắng và tất cả đều có trong từ điển, nếu không thì trả về false.
s rỗng luôn có thể tách được.
Bạn phải sử dụng lớp Trie (được cung cấp trong trie cùng với trienode), không dùng các kiểu dữ liệu dựng sẵn của ngôn ngữ như tập hợp, từ điển hoặc bản đồ để đếm/theo dõi.
Tự làm thử
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "solution.h"
int main() {
char s[4096], dLine[4096];
if (!fgets(s, sizeof(s), stdin)) s[0] = 0;
if (!fgets(dLine, sizeof(dLine), stdin)) dLine[0] = 0;
s[strcspn(s, "\r\n")] = '\0';
dLine[strcspn(dLine, "\r\n")] = '\0';
char* d[1024]; int dn = 0;
char* tok = strtok(dLine, " \t");
while (tok && dn < 1024) { d[dn++] = tok; tok = strtok(NULL, " \t"); }
printf("%s\n", wordBreak(s, d, dn) ? "true" : "false");
return 0;
}
Tất cả bài học trong Cây tiền tố, chuỗi cấu trúc dữ liệu số 8
3Thử thách luyện tập
Tiền tố chung dài nhấtĐếm từ có tiền tốTự động hoàn thànhTừ dài nhất trong từ điểnTách từTự luyện tập: Trình biên dịch C online