Pemisahan Kata
Pelajaran 14 dari 14 dalam kursus Trie: Struktur Data Seri #8 di Coddy.
Diberikan sebuah string s dan dictionary berisi kata-kata, bisakah kita memecah s menjadi urutan kata-kata dari dictionary tanpa menyisakan apa pun? "leetcode" bisa dipecah menjadi "leet" + "code" jika keduanya ada di dictionary; "catsandog" tidak bisa dipecah dengan cara pemotongan apa pun.
Proses pemrograman dinamis dapat menyelesaikannya. Definisikan dp[i] sebagai apakah i karakter pertama dapat disegmentasikan? Mulai dengan dp[0] = true. Untuk setiap i dengan nilai dp[i] true, telusuri trie mulai dari posisi i dalam string; setiap kali penelusuran mencapai node isEndOfWord pada indeks j, tetapkan dp[j+1] = true.
Trie membuat setiap penelusuran berjalan cepat: satu karakter yang tidak ditemukan akan mengakhirinya. Jawaban akhir ada di dp[n].
Tantangan
SedangTulis fungsi wordBreak yang menerima string s dan array string dictionary, lalu mengembalikan true jika s dapat dipecah menjadi satu atau lebih bagian tanpa spasi yang semuanya ada di dalam dictionary, atau false jika tidak.
s yang kosong selalu dapat dipecah.
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 s[4096], dLine[4096];
if (!fgets(s, sizeof(s), stdin)) s[0] = 0;
if (!fgets(dLine, sizeof(dLine), stdin)) dLine[0] = 0;
s[strcspn(s, "\r\n")] = '\0';
dLine[strcspn(dLine, "\r\n")] = '\0';
char* d[1024]; int dn = 0;
char* tok = strtok(dLine, " \t");
while (tok && dn < 1024) { d[dn++] = tok; tok = strtok(NULL, " \t"); }
printf("%s\n", wordBreak(s, d, dn) ? "true" : "false");
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