En Uzun Ortak Önek
Coddy'nin Trie - Veri Yapıları Serisi #8 kursunda ders 10 / 14.
Sıradaki zorluklar, içlerinde bir Trie kullanmak üzere tasarlanmıştır.
Önceki derslerde oluşturduğunuz Trie ve TrieNode sınıflarını kullanın (bunlar soldaki dosyalarda size sunulmuştur). Her zorluk size, Trie yapısını KULLANAN bir fonksiyon yazacağınız yeni bir solution dosyası ile gelir.
İlk problemimiz: verilen bir kelime listesinde, hepsinin paylaştığı en uzun ortak öneki bulun. Her kelimeyi bir trie yapısına ekledikten sonra cevap, her adımda tam olarak bir çocuk var olduğu ve hiçbir düğüm kelime sonu (end-of-word) olmadığı sürece kökten aşağıya doğru giden yoldur.
Görev
KolayBir dize dizisi olan words alan ve dizideki her kelimenin öneki olan en uzun dizeyi döndüren bir longestCommonPrefix fonksiyonu yazın.
Eğer dizi boşsa veya ortak bir önek yoksa, 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 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 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;
}
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