Prefiks Bersama Terpanjang

Pelajaran 10 dari 14 dalam kursus Trie: Struktur Data Seri #8 di Coddy.

Tantangan berikut dirancang untuk menggunakan Trie.

Gunakan class Trie dan TrieNode yang kamu buat di pelajaran sebelumnya (class tersebut tersedia di file di sebelah kiri). Setiap tantangan menyediakan file solution baru untuk kamu gunakan menulis fungsi yang MENGGUNAKAN Trie.

Masalah pertama: diberikan sebuah list kata, temukan prefiks umum terpanjang yang dimiliki semuanya. Setelah memasukkan setiap kata ke dalam trie, jawabannya adalah jalur dari root ke bawah selama tepat satu child ada di setiap langkah dan tidak ada node yang merupakan akhir kata.

Tantangan

Mudah

Tulis fungsi longestCommonPrefix yang menerima array string words dan mengembalikan string terpanjang yang menjadi prefiks setiap kata dalam array.

Jika array kosong atau tidak ada prefiks umum, kembalikan string kosong.

Kamu harus menggunakan class Trie (disediakan dalam 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 = longestCommonPrefix(words, n);
    printf("%s\n", res);
    free(res);
    return 0;
}

Semua pelajaran di Trie: Struktur Data Seri #8

1Pengenalan

Pengenalan Apa Itu Trie?

2Proyek Trie

class TrieNode class Trie Sisipkan Cari Diawali Dengan Hapus Jumlah Kata

3Tantangan Latihan

Prefiks Bersama TerpanjangHitung Kata dengan Prefiks Pelengkapan Otomatis Kata Terpanjang dalam Dictionary Pemisahan Kata

Latihan sendiri: Compiler C online