Word Break

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

Hash kümesi kullanan aşağıdan yukarıya tablo yöntemi O(m × L + n × L²) zamanda çalışır; burada n , s uzunluğu; m , kelime sayısı ve L , en uzun kelimedir. Her konumda her kelimeyi karşılaştırmanın maliyeti O(n × m × L) olur. Basit özyineleme üstel zamandadır.

Q: Word Break dinamik programlama problemi mi yoksa bir grafik problemi mi?

Her ikisi de. Dinamik programlama olarak canEnd[i] , ilk i harfin bölünüp bölünemeyeceğini belirtir. Graf olarak her indeks bir düğümdür; aralarındaki harfler bir sözcük oluşturduğunda i ile j arasında bir kenar bulunur ve n 'in 0'dan erişilebilir olup olmadığını sorarsın. Genişlik öncelikli arama, tabloyla aynı işi yapar.

OrtaDinamik programlama Hashing

+10

Bir s dizgen ve bir wordDict sözcük listen var. s dizgesini wordDict içindeki sözcüklerden oluşan parçalara ayırabiliyorsan true, aksi takdirde false döndür.

Parçalar sıralarını korur ve birlikte s dizgesindeki her harfi tam olarak bir kez kullanır. Bir sözcük istediğin kadar kullanılabilir ve her sözcüğü kullanmak zorunda değilsin.

Fonksiyon

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

sstring: Kelimelere ayırılacak dize
wordDictstring-array: İstediğiniz sıklıkta kullanabileceğiniz kelimeler
Döndürürboolean: true, s sözlük sözcüklerine bölünebiliyorsa; aksi takdirde false

Kısıtlar

1 ≤ s.length ≤ 300
1 ≤ wordDict.length ≤ 1000
1 ≤ wordDict[i].length ≤ 20
s ve her kelime yalnızca küçük İngilizce harfler içerir.
wordDict içindeki kelimelerin hepsi birbirinden farklıdır.

Örnekler

Girdi: s = "sunflowerseed"wordDict = ["sun", "flow", "flower", "seed"]
Çıktı: true
Açıklama: Bunu sun, flower, seed şeklinde böl. sun'dan sonra flow'u almak, hiçbir kelimenin başlamadığı er'yi bırakır; bu yüzden uyan ilk kelime her zaman doğru olan değildir.

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

Girdi: s = "pineappletart"wordDict = ["pine", "apple", "pineapple", "tar"]
Çıktı: false
Açıklama: Hem pine + apple hem de pineapple geriye tart bırakır. Oraya yalnızca tar sığar; bu da tek başına bir t bırakır, dolayısıyla hiçbir kesim işe yaramaz.

Ek soru

Geçerli bir bölmenin kullanabileceği en az sayıda kelimeyi döndürün veya s bölünemiyorsa -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

Her seferinde tek bir kelimeye karar vermek işe yaramaz ve tüm kesim noktalarını denemek üstel zaman alır. Ancak s'nin geri kalanının kesilip kesilemeyeceği yalnızca nerede başladığına bağlıdır; dolayısıyla yalnızca n + 1 soru vardır. Aşağıda n, s'nin uzunluğu; m, kelime sayısı ve L, en uzun kelimenin uzunluğudur.

Her konumda her sözcüğü dene

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

Sezgi

İlk parça, s dizgesinin başladığı bir sözcük olmalıdır. Böyle her sözcüğü deneyin ve geriye kalan harfler hakkında aynı soruyu sorun; geriye hiçbir şey kalmaması, her harfin kesildiği anlamına gelir. Önce her ilk sözcüğü, ardından her ikinci sözcüğü denemek geçerli bir kesimi gözden kaçırmaz.

Aynı kalanları tekrar tekrar kontrol eder. 299 tane a harfinin ardından bir b harfi geldiğinde ve sözcükler a, aa ile başlayıp on tane aya kadar uzandığında, a'ları bloklara ayırmanın 10^89dan fazla yolu bye ulaşıp başarısız olur ve özyineleme bunların hepsini dener.

Algoritma

canSplit(start) işlevini yaz: start konumundan sona kadar olan harfler kesilebilir mi? start, s uzunluğuna eşitse true döndür.
s dizgesinin start konumunda içerdiği her sözcük için, canSplit(start + its length) değeri true ise true döndür.
Aksi takdirde false döndür. 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)

Önbellek kullanarak özyineleme

Sezgi

Kalan yanıtı yalnızca start değerine bağlıdır; bu değer n + 1 farklı değer alır. a'lardan oluşan örnekte, 20. indeksteki kalana onluk iki bloktan sonra, yirmi tek a'dan sonra ve sayısız başka yolla ulaşılır ve her seferinde false olur. Her start için yanıtı bir kez saklayıp yeniden kullanın.

Memo, false yanıtlarını da saklamalıdır. Bir true tüm aramayı hemen bitirir; dolayısıyla tekrarlanan işlemlerin tümü başarısız olan dallardadır.

Her başlangıç her kelimeyi dener ve en fazla L harfi karşılaştırır: O(n × m × L) zaman, en fazla 6 × 10^6 harf kontrolü ve O(n) alan.

Algoritma

Her indeks için bir yuva içeren bir önbellek oluşturun ve her birini henüz hesaplanmamış olarak işaretleyin.
canSplit(start) içinde, s'nin sonuna gelindiğinde true değerini; aksi hâlde yuvada kayıtlı bir yanıt varsa bu yanıtı döndürün.
Aksi hâlde, normal özyinelemede olduğu gibi her sözcüğü deneyin, sonucu yuvaya kaydedin (false dâhil) ve 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 karma kümesiyle aşağıdan yukarıya

Sezgi

Önekler üzerinde çalışın. canEnd[i], ilk i harfin kesilip kesilemeyeceğini göstersin; boş önek için hiçbir sözcük gerekmediğinden canEnd[0] değeri true olur. İlk end harf, son parçası start ile end arasındaki bir sözcük olduğunda ve canEnd[start] değeri true olduğunda kesilebilir. Soldan sağa doldurulduğunda, ihtiyacınız olan her canEnd[start] değeri zaten bilinir.

Sözcükleri bir hash kümesine koyun. Hiçbir sözcük L harften uzun olmadığından, sözlük ne kadar büyük olursa olsun yalnızca end konumunda biten L parça eşleşebilir. sunflowerseed üzerinde canEnd, 0, 3, 7, 9 ve 13 konumlarında true değerini alır; 7 konumundaki çıkmaz sorun yaratmaz.

n konumun her biri en fazla L parçaya bakar ve her parçayı oluşturup hash'lemek en fazla L adım alır: O(n × L²), en fazla 1.2 × 10^5 adım; ayrıca küme için O(m × L).

Algoritma

Kelimeleri bir hash kümesine yerleştir; en uzun uzunluğu L olarak not et.
n + 1 girişli, tüm değerleri false olan canEnd oluştur ve canEnd[0] değerini true olarak ayarla.
1'den n'e kadar her end değeri ve 1'den min(L, end)'e kadar her length değeri için: 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 döngüden çık.
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

Greedy kesim yapmak. En uzunla başlamak, carpetal sözcüğünü carpet olarak kesip al parçasını boşa çıkarır; oysa car + petal işe yarar. En kısa ile başlamak ise sunflowerseed sözcüğünde takılıp kalır.
Yalnızca true yanıtlarını bellekte tutmak. Tekrarlanan iş false dallarında olduğundan, a'lardan oluşan örnek üstel kalır.
Tabloda bir eksik giriş bırakmak. canEnd, 0'dan n'e kadar önek uzunlukları için n + 1 giriş gerektirir.
s'nin sonunu aşacak şekilde karşılaştırma yapmak; örneğin abc sözcüğünü ab kalanıyla karşılaştırmak. Önce uzunlukları kontrol et.
Lua ve R'de dizge konumları 1'den başlar: e harfinde biten k uzunluğundaki parça, e-k+1 konumundan başlar.

Sıkça sorulan sorular3

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

Hash kümesi kullanan aşağıdan yukarıya tablo yöntemi O(m × L + n × L²) zamanda çalışır; burada n, s uzunluğu; m, kelime sayısı ve L, en uzun kelimedir. Her konumda her kelimeyi karşılaştırmanın maliyeti O(n × m × L) olur. Basit özyineleme üstel zamandadır.

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

Her ikisi de. Dinamik programlama olarak canEnd[i], ilk i harfin bölünüp bölünemeyeceğini belirtir. Graf olarak her indeks bir düğümdür; aralarındaki harfler bir sözcük oluşturduğunda i ile j arasında bir kenar bulunur ve n'in 0'dan erişilebilir olup olmadığını sorarsın. Genişlik öncelikli arama, tabloyla aynı işi yapar.

True veya false döndürmek yerine her cümleyi nasıl listelersin?

Geri izleme: Her indekste uyan her sözcüğü dene, kalanın üzerinde özyinelemeli çağrı yap ve her indeks için cümle listesini hatırla. Önce doğru veya yanlış tablosunu çalıştır; böylece bölünemeyen bir dize aramayı atlar. Cümlelerin sayısı üstel olarak artabilir, bu nedenle çalışma süresini çıktı boyutu belirler.

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

Test #1

Test #2

Test #3

Argümanlar

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

Beklenen Çıktı

true

Word Break

Fonksiyon

Kısıtlar

Örnekler

İpuçları

Çözüm

Her konumda her sözcüğü dene

Önbellek kullanarak özyineleme

Önekler üzerinde karma kümesiyle aşağıdan yukarıya

Tuzaklar ve uç durumlar

Sıkça sorulan sorular3

Benzer problemler