Từ dài nhất trong từ điển

Bài học 13 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 trước một từ điển gồm các từ, hãy tìm từ dài nhất có thể được tạo thành từng ký tự một bằng cách nối thêm ký tự vào một từ đã có trong từ điển. "world" chỉ được tính nếu "w", "wo", "wor" và "worl" cũng đều là các từ được lưu trong từ điển.

Trie rất phù hợp cho bài toán này. Chèn mọi từ, sau đó duyệt DFS từ nút gốc, nhưng chỉ đi xuống nút con nếu nút đó được đánh dấu isEndOfWord. Nhờ vậy, mỗi nút ta đi qua trong quá trình duyệt DFS đều biểu thị một đường đi mà mọi tiền tố của nó cũng là một từ.

Theo dõi đường đi dài nhất. Nếu hai đường đi có cùng độ dài, hãy chọn đường đi có thứ tự từ điển nhỏ hơn.

Thử thách

Trung bình

Viết một hàm longestWordInDict nhận một mảng chuỗi words và trả về từ dài nhất có thể tạo bằng cách lần lượt thêm từng ký tự vào một từ ngắn hơn trong mảng.

Nếu hai từ có độ dài bằng nhau, hãy trả về từ có thứ tự từ điển nhỏ hơn. Nếu mảng rỗng, hãy trả về một chuỗi rỗng.

Bạn phải 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 có sẵn của ngôn ngữ như tập hợp, từ điển hoặc bản đồ để đếm hay theo dõi.

Tự làm thử

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "solution.h"

int main() {
    char line[4096];
    if (!fgets(line, sizeof(line), stdin)) line[0] = 0;
    line[strcspn(line, "\r\n")] = '\0';
    char* words[1024]; int n = 0;
    char* tok = strtok(line, " \t");
    while (tok && n < 1024) { words[n++] = tok; tok = strtok(NULL, " \t"); }
    char* res = longestWordInDict(words, n);
    printf("%s\n", res);
    free(res);
    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

1Giới thiệu

Giới thiệu Trie là gì?

2Dự án Trie

Lớp TrieNode Lớp Trie Chèn Tìm kiếm Bắt đầu bằng Xóa Số lượng từ

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