Kata Terpanjang dalam Dictionary
Pelajaran 13 dari 14 dalam kursus Trie: Struktur Data Seri #8 di Coddy.
Diberikan sebuah dictionary berisi kata-kata, cari kata terpanjang yang dapat dibentuk satu karakter setiap kali dengan menambahkan karakter ke kata yang sudah ada di dalam dictionary. "world" hanya dihitung jika "w", "wo", "wor", dan "worl" juga tersimpan sebagai kata.
Masalah ini sangat cocok diselesaikan dengan trie. Masukkan setiap kata, lalu lakukan DFS dari akar, tetapi hanya lanjut ke child jika ditandai dengan isEndOfWord. Dengan begitu, setiap node yang kita kunjungi selama DFS mewakili jalur yang setiap prefiksnya juga merupakan kata.
Lacak jalur terpanjang. Jika dua jalur memiliki panjang yang sama, pilih jalur yang lebih kecil secara leksikografis.
Tantangan
SedangTulis fungsi longestWordInDict yang menerima array string words dan mengembalikan kata terpanjang yang dapat dibentuk dengan menambahkan satu karakter setiap kali pada kata yang lebih pendek di dalam array.
Jika dua kata memiliki panjang yang sama, kembalikan kata yang lebih kecil secara leksikografis. Jika array kosong, kembalikan string kosong.
Kamu harus menggunakan class Trie (tersedia 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 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;
}
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