Sözlükteki En Uzun Kelime
Coddy'nin Trie - Veri Yapıları Serisi #8 kursunda ders 13 / 14.
Verilen bir kelime sözlüğünde, sözlükte zaten bulunan bir kelimeye ekleme yaparak her seferinde bir karakter eklenerek oluşturulabilecek en uzun kelimeyi bulun. "world" kelimesi, yalnızca "w", "wo", "wor" ve "worl" kelimelerinin tümü de saklanan kelimeler arasındaysa sayılır.
Bu, bir trie için mükemmel bir uyumdur. Her kelimeyi ekleyin, ardından kökten DFS yapın - ancak bir alt düğüme yalnızca isEndOfWord olarak işaretlenmişse inin. Bu sayede, DFS sırasında ziyaret ettiğimiz her düğüm, her önekin kendisinin de bir kelime olduğu bir yolu temsil eder.
En uzun yolu takip edin. Eğer iki yol aynı uzunluktaysa, sözlük sırasına göre daha küçük olanı seçin.
Görev
OrtaBir dize dizisi words alan ve dizideki daha kısa bir kelimeye her seferinde bir karakter eklenerek oluşturulabilen en uzun kelimeyi döndüren bir longestWordInDict fonksiyonu yazın.
Eğer iki kelime uzunluk bakımından eşitse, sözlükbilimsel (lexicographically) olarak daha küçük olanı döndürün. Eğer dizi boşsa, boş bir dize döndürün.
Trie sınıfını kullanmalısınız (trienode ile birlikte trie içinde sağlanmıştır) - sayma veya izleme işlemleri için kümeler (sets), sözlükler (dicts) veya eşlemler (maps) 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 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;
}
Trie - Veri Yapıları Serisi #8 bölümündeki tüm dersler
3Pratik Zorluklar
En Uzun Ortak ÖnekÖnek İçeren Kelimeleri SayOtomatik TamamlamaSözlükteki En Uzun KelimeKelime Bölme