Pelengkapan Otomatis
Pelajaran 12 dari 14 dalam kursus Trie: Struktur Data Seri #8 di Coddy.
Ini adalah kasus penggunaan klasik untuk trie: berdasarkan apa yang telah diketik pengguna sejauh ini, tampilkan setiap kata tersimpan yang diawali dengan prefiks tersebut. Telusuri hingga node prefiks; jika kamu tidak bisa mencapainya, jangan kembalikan apa pun. Lalu telusuri subtree di bawahnya dan kumpulkan setiap kata yang kamu temukan.
Saat kamu menelusuri ke bawah selama DFS, susun kata secara bertahap dengan menambahkan karakter dari edge yang baru saja kamu lewati. Setiap kali kamu mencapai node tempat isEndOfWord bernilai true, jalur saat ini adalah salah satu kecocokan.
Tantangan
SedangTulis fungsi autocomplete yang menerima array string words dan string prefix, lalu mengembalikan list kata dari array yang diawali dengan prefix.
List yang dikembalikan harus dalam urutan menaik (abjad). Jika tidak ada kata yang cocok, kembalikan list kosong.
Kamu harus menggunakan class Trie (disediakan di trie bersama trienode). Jangan gunakan fitur bawaan bahasa seperti set, dict, atau map untuk menghitung atau melacak.
Coba sendiri
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "solution.h"
int main() {
char l1[4096], prefix[1024];
if (!fgets(l1, sizeof(l1), stdin)) l1[0] = 0;
if (!fgets(prefix, sizeof(prefix), stdin)) prefix[0] = 0;
l1[strcspn(l1, "\r\n")] = '\0';
prefix[strcspn(prefix, "\r\n")] = '\0';
char* words[1024]; int n = 0;
char* tok = strtok(l1, " \t");
while (tok && n < 1024) { words[n++] = tok; tok = strtok(NULL, " \t"); }
int out_n = 0;
char** res = autocomplete(words, n, prefix, &out_n);
for (int i = 0; i < out_n; i++) { printf("%s", res[i]); if (i + 1 < out_n) printf(" "); }
printf("\n");
if (res) free(res);
return 0;
}
Semua pelajaran di Trie: Struktur Data Seri #8
3Tantangan Latihan
Prefiks Bersama TerpanjangHitung Kata dengan PrefiksPelengkapan OtomatisKata Terpanjang dalam DictionaryPemisahan KataLatihan sendiri: Compiler C online