Tiền tố chung dài nhất

Bài học 10 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.

Các thử thách tiếp theo được thiết kế để sử dụng Trie.

Dùng các lớp Trie và TrieNode mà bạn đã xây dựng trong các bài học trước (các lớp này có sẵn trong những tệp bên trái). Mỗi thử thách cung cấp cho bạn một tệp solution mới, nơi bạn viết một hàm sử dụng Trie.

Bài toán đầu tiên: cho một danh sách các từ, hãy tìm tiền tố chung dài nhất của chúng. Sau khi chèn mọi từ vào trie, đáp án là đường đi từ nút gốc xuống dưới, tiếp tục khi mỗi bước có đúng một nút con và không có nút nào đánh dấu kết thúc từ.

Thử thách

Dễ

Viết hàm (function) longestCommonPrefix nhận một mảng chuỗi words và trả về chuỗi dài nhất là tiền tố của mọi từ trong mảng.

Nếu mảng rỗng hoặc không có tiền tố chung, hãy trả về 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 tích hợp 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 = longestCommonPrefix(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ành Từ dài nhất trong từ điển Tách từ

Tự luyện tập: Trình biên dịch C online