Kelime Bölme
Coddy'nin Trie - Veri Yapıları Serisi #8 kursunda ders 14 / 14.
Bir s dizesi ve bir kelime sözlüğü verildiğinde, s dizesini hiçbir şey artmayacak şekilde sözlükteki kelimelerden oluşan bir diziye bölebilir miyiz? Eğer her ikisi de sözlükte varsa "leetcode", "leet" + "code" şeklinde ayrılır; "catsandog" ise nasıl kesersek keselim ayrılmaz.
Dinamik programlama yaklaşımı bu sorunu çözer. dp[i] değerini ilk i karakter bölümlenebilir mi? olarak tanımlayın. dp[0] = true ile başlayın. dp[i] değerinin true olduğu her i için, dizedeki i konumundan başlayarak trie üzerinde ilerleyin; ilerleme her j dizinindeki bir isEndOfWord düğümüne ulaştığında, dp[j+1] = true olarak ayarlayın.
Trie yapısı her ilerlemeyi hızlandırır: tek bir eksik karakter ilerlemeyi sonlandırır. Nihai cevap dp[n] içindedir.
Görev
OrtaBir s dizesi ve bir dictionary dize dizisi alan ve s dizesinin tamamı sözlükte bulunan bir veya daha fazla boşluksuz parçaya bölünüp bölünemeyeceğini belirleyen bir wordBreak fonksiyonu yazın. Bölünebiliyorsa true, aksi takdirde false döndürmelidir.
Boş bir s dizesi her zaman bölünebilir kabul edilir.
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 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;
}
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