Otomatik Tamamlama

Coddy'nin Trie - Veri Yapıları Serisi #8 kursunda ders 12 / 14.

Bu, bir trie için klasik kullanım durumudur: kullanıcının şu ana kadar yazdıklarına dayanarak, bu önekle başlayan tüm kayıtlı kelimeleri listeleyin. Önek düğümüne gidin; gidemiyorsanız hiçbir şey döndürmeyin. Ardından aşağıdaki alt ağacı keşfedin ve bulduğunuz her kelimeyi toplayın.

DFS sırasında aşağı doğru ilerlerken, az önce geçtiğiniz kenarın karakterini ekleyerek kelimeyi kademeli olarak oluşturun. isEndOfWord değerinin true olduğu bir düğüme her ulaştığınızda, mevcut yol eşleşmelerden biridir.

Görev

Orta

Bir dize dizisi words ve bir dize prefix alan ve dizideki prefix ile başlayan kelimelerin listesini döndüren bir autocomplete fonksiyonu yazın.

Döndürülen liste artan (alfabetik) sırada olmalıdır. Hiçbir kelime eşleşmezse, boş bir liste döndürün.

Trie sınıfını kullanmalısınız (trienode ile birlikte trie içinde sağlanmıştır) - sayma/izleme işlemleri için set, dict veya map gibi dile özgü yerleşik yapıları kullanmayın.

Kendin dene

#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;
}

Trie - Veri Yapıları Serisi #8 bölümündeki tüm dersler

1Giriş

Giriş Trie Nedir?

2Trie Projesi

TrieNode Sınıfı Trie Sınıfı Ekleme Arama StartsWith Silme Kelime Sayısı

3Pratik Zorluklar

En Uzun Ortak Önek Önek İçeren Kelimeleri SayOtomatik TamamlamaSözlükteki En Uzun Kelime Kelime Bölme