Word Break

+10

Bir s dizgeniz ve bir wordDict sözcük listeniz var. s dizgesini, her parçası wordDict içindeki bir sözcük olacak şekilde parçalara ayırabiliyorsanız true, aksi hâlde false döndürün.

Parçalar sıralarını korur ve birlikte s dizgesindeki her harfi tam olarak bir kez kullanır. Bir sözcük istediğiniz kadar kullanılabilir ve tüm sözcükleri kullanmanız gerekmez.

Fonksiyon

wordBreak(s: string, wordDict: string-array) → boolean

sstring: kelimelere bölünecek dize
wordDictstring-array: Her birini istediğin kadar kullanabileceğin kelimeler
Döndürürboolean: s sözlük sözcüklerine ayrılabiliyorsa true, aksi halde false

Kısıtlar

1 ≤ s.length ≤ 300
1 ≤ wordDict.length ≤ 1000
1 ≤ wordDict[i].length ≤ 20
s ve her sözcük yalnızca küçük İngilizce harfler içerir.
The words in wordDict birbirinden farklıdır.

Örnekler

Girdi: s = "sunflowerseed"wordDict = ["sun", "flow", "flower", "seed"]
Çıktı: true
Açıklama: Onu sun, flower, seed şeklinde böl. sun'dan sonra flow almak hiçbir yere götürmez; çünkü geriye kalan er ile başlayan bir kelime yoktur. Bu nedenle, uyan ilk kelime her zaman doğru kelime değildir.

Girdi: s = "bananaban"wordDict = ["ban", "ana"]
Çıktı: true
Açıklama: ban + ana + ban dizgeyi kapsar ve ban ifadesini iki kez kullanır; buna izin verilir.

Girdi: s = "pineappletart"wordDict = ["pine", "apple", "pineapple", "tar"]
Çıktı: false
Açıklama: Dize pine + apple ile ya da pineapple ile başlar ve her iki durumda da geriye tart kalır. Buraya uyan tek sözcük tar olur; geriye tek başına bir t kalır, dolayısıyla hiçbir kesim işe yaramaz.

Gönderirken +21 gizli test

Ek soru

Geçerli bir kesmede kullanılabilecek en az sözcük sayısını döndürün ya da s kesilemiyorsa -1 döndürün. Tabloda ne değişir ve çalışma süresi değişir mi?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Açgözlü biçimde kesmek her iki yönde de başarısız olur: önce en kısa sözcüğü almak sunflowerseed sözcüğünü sun + flow biçiminde keser; önce en uzun sözcüğü almaksa carpetal sözcüğünü carpet olarak keser ve al parçasını ortada bırakır. Bu yüzden seçenekleri denemeniz gerekir ve bir dize üstel sayıda farklı şekilde kesilebilir. Bunu çözen şey, dizenin geri kalanının kesilip kesilemeyeceğinin yalnızca geri kalan kısmın nereden başladığına bağlı olmasıdır; dolayısıyla yalnızca n + 1 farklı soru vardır. Aşağıda, n, s dizisinin uzunluğu; m, sözcük sayısı ve L, en uzun sözcüğün uzunluğudur.

Her konumda her kelimeyi dene

Doğru, ama en büyük testlerde bitmiyor

Sezgi

s dizgesini soldan okuyun. İlk parça ne olursa olsun, s dizgesinin onunla başlaması gerekir. Bu tür her sözcüğü deneyin ve her biri için geriye kalan harflerle ilgili aynı soruyu sorun. Herhangi bir sözcük tam bir bölmeye yol açarsa yanıt true olur. Hiçbiri yol açmazsa false olur. Geriye hiçbir şey kalmadığında her harfi bölmüşsünüzdür; bu da başarı sayılır.

Bu yöntem olası her ilk sözcüğü, sonra olası her ikinci sözcüğü ve bu şekilde devamını dener; dolayısıyla geçerli bir bölmeyi gözden kaçırmaz ve döndürdüğü her true gerçek bir bölmeyle birlikte gelir.

Aynı kalanları tekrar tekrar kontrol ettiği için yavaştır. On adet a harfine kadar a, aa ve benzeri sözcükleri ele alalım; önce 299 tane a, ardından bir b olsun. a'ları en fazla on harflik bloklara ayırmanın her yolu b'ye ulaşır ve orada başarısız olur; üstelik bu tür yolların sayısı 10^89'dan fazladır. Özyineleme, false yanıtını verebilmek için hepsini denemek zorundadır.

Algoritma

Harflerin start indeksinden sonuna kadar sözcüklere ayrılıp ayrılamayacağını belirten bir yardımcı canSplit(start) yazın.
start, s uzunluğuna eşitse true döndürün.
Her sözcük için s dizgesinin start indeksinden başlayarak bu sözcüğü içerip içermediğini kontrol edin.
İçeriyorsa ve canSplit(start + length of the word) değeri true ise true döndürün.
Hiçbir sözcük işe yaramazsa false döndürün. Yanıt canSplit(0) değeridir.

def wordBreak(s, wordDict):
    def can_split(start):
        # Can s[start:] be cut into dictionary words?
        if start == len(s):
            return True  # nothing left to cut
        for word in wordDict:
            if s.startswith(word, start) and can_split(start + len(word)):
                return True
        return False

    return can_split(0)

Önbellekli özyineleme

Sezgi

Kalanın yanıtı yalnızca nereden başladığına bağlıdır ve start yalnızca n + 1 değer alır. a örneğinde, 20. indekste başlayan kalana iki onluk bloktan sonra, yirmi tek a'dan sonra ve çok sayıda başka yolla ulaşılır; yanıtı her seferinde false'tur. Her başlangıç için yanıtı ilk hesapladığında sakla ve daha sonra geri oku.

Bir memo yuvasının üç duruma ihtiyacı vardır: henüz hesaplanmadı, true ve false. Önemli olan false yanıtlarıdır. Bir true tüm aramayı hemen bitirir; bu yüzden yalın özyinelemenin tekrarladığı iş, başarısız olan dalların tamamındadır.

Her başlangıç bir kez hesaplanır ve her sözcüğü dener; bu sırada en fazla L harfi karşılaştırılır. Dolayısıyla zaman karmaşıklığı O(n × m × L) olur: burada en fazla 300 × 1000 × 20 = 6 × 10^6 harf kontrolü yapılır. Memo ve çağrı yığını O(n) alan kullanır ve çağrılar en fazla 300 derinliğe kadar iç içe geçer.

Algoritma

Her indeks için, her biri henüz hesaplanmadı olarak işaretlenmiş bir yuva içeren bir not tablosu oluşturun.
canSplit(start) içinde, dizenin sonuna gelindiğinde true döndürün ve start için yuvada bir yanıt varsa kaydedilmiş yanıtı döndürün.
Aksi takdirde, düz özyinelemede olduğu gibi start konumunda başlayan her sözcüğü deneyin ve geri kalanın bölünebildiği ilk sözcükte durun.
false da dahil olmak üzere sonucu yuvaya kaydedin ve döndürün.
canSplit(0) döndürün.

def wordBreak(s, wordDict):
    memo = [None] * len(s)  # memo[start]: answer for s[start:], None until worked out

    def can_split(start):
        if start == len(s):
            return True
        if memo[start] is not None:
            return memo[start]
        result = False
        for word in wordDict:
            if s.startswith(word, start) and can_split(start + len(word)):
                result = True
                break
        memo[start] = result
        return result

    return can_split(0)

Önekler üzerinde hash kümesiyle alttan yukarıya

Sezgi

Yönü tersine çevir ve önekler üzerinde çalış. canEnd[i], ilk i harfin sözcüklere ayrılıp ayrılamayacağını göstersin. Boş önek için sözcük gerekmez, bu yüzden canEnd[0] değeri true olur. İlk end harf, son parçası, yani start ile end arasındaki harfler bir sözcük olduğunda ve ondan önceki harfler sözcüklere ayrılabildiğinde ayrılabilir; başka bir deyişle, canEnd[start] değeri true olmalıdır. Tabloyu soldan sağa doldur; böylece ihtiyaç duyduğun her canEnd[start] değeri zaten biliniyor olur.

Her konumda tüm m sözcüğü karşılaştırmak yerine, sözcükleri bir karma kümesine koy ve olası son parçaları burada ara. Hiçbir sözcük L harften uzun olmadığından, yalnızca end konumunda biten L parça eşleşebilir. sunflowerseed üzerinde canEnd, 0'da, 3'te (sun), 7'de (flow), 9'da (flower) ve 13'te (9. konumdan sonraki seed) true olur; dolayısıyla yanıt true olur. 7. konum bir yere varmaz, çünkü er ile başlayan hiçbir sözcük yoktur; tablo bunu önemsemez.

n konum vardır, her biri en fazla L parça arar ve bir parçayı oluşturmak ve karma değerini hesaplamak en fazla L adım sürer. Bu, sözlük ne kadar büyük olursa olsun en fazla 300 × 20 × 20 = 1.2 × 10^5 harf adımıyla O(n × L²) demektir. Kümenin oluşturulması her sözcüğü bir kez okur: O(m × L). Dolayısıyla toplam karmaşıklık O(m × L + n × L²) olur. Küme O(m × L) harf tutar ve tabloda n + 1 bayrak bulunur. Özyineleme yoktur.

Algoritma

Her sözcüğü bir hash kümesine ekle ve en uzun sözcüğün L uzunluğunu not et.
n + 1 elemanlı, tümü false olan bir canEnd oluştur ve canEnd[0] değerini true olarak ayarla.
1'den n'ye kadar her end için, 1'den min(L, end)'e kadar her length değerini dene.
canEnd[end-length] değeri true ise ve end konumunda biten bu uzunluktaki parça kümede bulunuyorsa, canEnd[end] değerini true olarak ayarla ve uzunlukları denemeyi bırak.
canEnd[n] değerini döndür.

def wordBreak(s, wordDict):
    words = set(wordDict)
    longest = max(len(word) for word in wordDict)
    n = len(s)
    # can_end[i]: the first i letters split into dictionary words
    can_end = [False] * (n + 1)
    can_end[0] = True  # the empty prefix needs no words
    for end in range(1, n + 1):
        # The last word is s[end-length:end], and no word is longer than longest.
        for length in range(1, min(longest, end) + 1):
            if can_end[end - length] and s[end - length:end] in words:
                can_end[end] = True
                break
    return can_end[n]

Tuzaklar ve uç durumlar

Çoğu yanlış yanıt, bir kesme noktasını çok erken seçmekten veya başarısızlıklarını hiç hatırlamayan bir aramadan kaynaklanır.

Açgözlü kesme yapmak. Önce en uzun sözcüğü almak, carpetal sözcüğünü carpet olarak keser ve geriye al kalır; oysa car + petal işe yarar. Önce en kısa sözcüğü almak ise sunflowerseed için başarısız olur.
Yalnızca s içindeki her harfin herhangi bir sözcükte göründüğünü kontrol etmek. aaaa ve aa sözcükleriyle her parçanın uzunluğu çift olur; bu nedenle yedi harfli aaaaaaa kesilemez.
Yalnızca true yanıtlarını not belleğinde saklamak. true zaten aramayı bitirir. Tekrarlanan iş false dallarındadır; dolayısıyla bunları içermeyen bir not belleği üstel kalır.
Tabloyu bir eleman eksik oluşturmak. canEnd[i], ilk i harfle ilgilidir ve hem 0 hem de n geçerli olduğundan n + 1 elemana ihtiyaç vardır.
Bir sözcük geriye kalandan uzunsa, örneğin abc sözcüğünü ab ile karşılaştırırken, s dizgesinin sonunun ötesine geçmek. Harfleri karşılaştırmadan önce uzunlukları kontrol edin.
Lua ve R'de dizge konumları 1'den başlar: e harfinde biten, uzunluğu k olan bir parça e-k+1 harfinde başlar.

Sıkça sorulan sorular4

Word Break'in zaman karmaşıklığı nedir?

Karma değerleri baştan sona hesaplayan tablo ve hash kümesi O(m × L + n × L²) zamanda çalışır; burada n, s dizgesinin uzunluğu, m sözcük sayısı ve L en uzun sözcüğün uzunluğudur. Kümeyi oluşturmak her sözcüğü bir kez okur ve n konumun her biri, uzunluğu en fazla L harf olan en fazla L parçayı arar. Bunun yerine her konumda her sözcüğü karşılaştırırsanız, süre O(n × m × L) olur. Bellek kullanmayan yalın özyineleme üstel zaman alır.

Word Break için açgözlü bir yaklaşım neden başarısız olur?

Açgözlü bir kural tek bir sözcüğe bağlanır ve onu asla yeniden değerlendirmez. En uzunu önce seçmek carpetal sözcüğünü carpet ve al olarak bölerken, car + petal işe yarar. En kısayı önce seçmek sunflowerseed sözcüğünü sun + flow olarak böler ve erseed üzerinde takılıp kalır. Dinamik programlama, herhangi bir bölmenin ulaşabileceği her konumu korur; böylece doğru seçeneği asla kaybetmez.

Word Break bir dinamik programlama problemi mi yoksa bir graf problemi mi?

Her iki bakış açısı da işe yarar. Dinamik programlama yaklaşımında canEnd[i], daha küçük öneklerden oluşturularak ilk i harfin bölünüp bölünemeyeceğini yanıtlar. Grafik yaklaşımında her dizin bir düğümdür ve i ile j arasındaki harfler bir sözcük oluşturduğunda i düğümünden j düğümüne bir kenar bulunur; sorulan, n düğümüne 0 düğümünden ulaşılıp ulaşılamayacağıdır. Ziyaret edilmiş düğümler kümesi kullanan bir genişlik öncelikli arama, tabloyla aynı işi yapar.

True ya da false döndürmek yerine her cümleyi nasıl listelersiniz?

Geri izlemeyi kullanın: her dizinde, uyan her sözcüğü deneyin ve kalan kısım için özyinelemeli çağrı yaparak ilerledikçe cümleyi oluşturun. Her kalan kısmın yalnızca bir kez çözümlenmesi için her dizindeki cümle listesini hatırlayın. Önce doğru veya yanlış tablosunu çalıştırın; böylece bölünemeyen bir dize arama adımını atlar. Cümle sayısı üstel olarak artabileceğinden, çıktı kümesinin boyutu çalışma süresini belirler.

Python

def wordBreak(s, wordDict):
    # Kodu buraya yazın

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

s = "sunflowerseed"
wordDict = ["sun", "flow", "flower", "seed"]

Beklenen

true

Word Break

Fonksiyon

Kısıtlar

Örnekler

İpuçları

Çözüm

Her konumda her kelimeyi dene

Önbellekli özyineleme

Önekler üzerinde hash kümesiyle alttan yukarıya

Tuzaklar ve uç durumlar

Sıkça sorulan sorular4

Benzer problemler