Word Search

Q: Word Search'ün zaman karmaşıklığı nedir?

En kötü durum, m × n boyutunda bir tahta ve L uzunluğunda bir sözcük için O(m·n·3^L) şeklindedir. m·n hücrenin her biri bir yol başlatabilir ve ilk adımdan sonra her hücrenin denenebilecek en fazla üç ziyaret edilmemiş komşusu vardır. Ek alan, özyineleme için O(L) , ayrıca tahtayı işaretlemek için kopyalarsanız O(m·n) olur.

OrtaGeri izleme Graflar

+10

Sana, harflerden oluşan bir ızgara olan board veriliyor; bu, board[r][c] değerinin r satırındaki, c sütunundaki harf olduğu bir dizge listesi ve bir word dizgesidir.

Izgarada word dizgesini izleyebiliyorsan true döndür: herhangi bir hücreden başla ve her adımda mevcut hücrenin doğrudan üstündeki, altındaki, solundaki veya sağındaki hücreye geç; böylece ziyaret ettiğin hücreler sırayla word dizgesini oluşturur. Bir izleme aynı hücreyi iki kez kullanamaz. Aksi takdirde false döndür. Harfler büyük/küçük harfe duyarlıdır; dolayısıyla a ile A farklıdır.

Fonksiyon

exist(board: string-array, word: string) → boolean

boardstring-array: ızgara, her satırda bir harf dizisi
wordstring: iz sürmek için kullanılan sözcük
Döndürürboolean: kelimenin, her biri en fazla bir kez kullanılan yan yana hücreler üzerinden izlenip izlenemeyeceği

Kısıtlar

1 ≤ board.length ≤ 6
1 ≤ board[i].length ≤ 6 ve tüm satırlar aynı uzunluktadır.
1 ≤ word.length ≤ 20
board ve word yalnızca büyük ve küçük İngilizce harfler içerir.

Örnekler

Girdi: board = ["STAR", "POOL", "ENDS"]word = "STOOLS"
Çıktı: true
Açıklama: 0. satır, 0. sütundaki S harfinden başlayın, ardından sağa giderek T harfine, aşağı inerek O harfine, sağa giderek ikinci O harfine, sağa giderek L harfine ve aşağı inerek 2. satır, 3. sütundaki S harfine ulaşın. Bu, her biri bir öncekine bitişik olan altı farklı hücredir.

Girdi: board = ["STAR", "POOL", "ENDS"]word = "POP"
Çıktı: false
Açıklama: Tahtada 1. satır, 0. sütunda tek bir P var. P ve O'dan sonra bir P daha gerekiyor ve tek olan da yolun başladığı hücre; bu hücre iki kez kullanılamaz.

Girdi: board = ["STAR", "POOL", "ENDS"]word = "SAND"
Çıktı: false
Açıklama: SAND harfinin her biri tahtada, ancak yol ilk adımda kesiliyor: tek A, 0. satır 2. sütunda ve iki S de ona bitişik değil.

Gönderirken +23 gizli test

Ek soru

Evet ya da hayır demek yerine, tahtada word sözcüğünün kaç farklı izinin bulunduğunu sayabilir misin?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Bunun yanıtı bir formülle bulunmaz: ızgaradaki yolları aramanız gerekir. Geri izleme bunu her seferinde bir yolu ele alarak yapar. Yolu bir harf uzatırsınız, yol hücreyi kullandığı sürece hücreyi işaretlersiniz ve geri dönerken işareti kaldırırsınız; böylece bir hücre aynı yol içinde asla yeniden kullanılmaz, ancak diğer tüm yollar için serbest kalır. Bu arama, en kötü durumda sözcüğün uzunluğuna göre üstel zaman alır; en fazla 6 × 6 boyutundaki bir tahtada bu sorun değildir. Öncesinde yapılan iki ucuz kontrol, harf sayımı ve sözcüğün daha nadir bulunan ucundan başlamak, gereken adım sayısını genellikle on binlerden birkaç düzineye düşürür.

ziyaret edilmiş bir ızgarayla geri izleme

Sezgi

Bir karar ağacı düşün. İlk seçim başlangıç hücresidir ve word[0] değerini içermelidir. Bundan sonra her düğüm, ilk i harfi yazan bir yoldur; çocukları ise word[i] değerini içeren ve henüz yol üzerinde olmayan komşulardır. Kelimenin tamamını yazan bir yol başarıya ulaşır. Böyle bir komşusu olmayan yol çıkmaz sokaktır ve sonraki seçeneği denemek için geri dönersin.

visited ızgarası, her hücrenin yalnızca bir kez kullanılmasını sağlar. Yol bir hücreye adım attığında hücreyi işaretle, yol hücreden geri çıktığında ise işareti kaldır. Geri izlemeyi sağlayan bu işareti kaldırma işlemidir: çıkmaz sokakta geçilen bir hücre, sonraki denemede kullanılabilmesi için yeniden boş olmalıdır. AA / AB tahtasında AAA kelimesini ararken sol üst hücreden başlarsan, aşağı gitmek sol altta takılıp kalır (diğer komşusu B’dir); sağa gitmek ise sağ üstte takılıp kalır. Bu hücreler işaretli kalsaydı, sol alt, sonra sol üst, sonra sağ üst şeklindeki yanıt asla bulunamazdı.

Bu standart yanıttır; burada doğru çalışır ve yeterince hızlıdır. Maliyeti, araştırdığı yolların sayısıdır. İlk adımdan sonra her adımda en fazla üç yeni yön denenebilir; bu nedenle L harfli bir kelime, yaklaşık m·n·3^L yol anlamına gelebilir. Tamamı A olan 5 × 5 boyutlarında bir tahta ve ardından bir B gelen 8 A harfli kelime düşün. Her A yol geçerli bir önektir ve arama, hiç B olmadığını anlayana kadar bunların hepsini dolaşır: false yanıtını vermek için yaklaşık 65,000 hücre kontrolü gerekir. Her ek harf bu sayıyı kabaca ikiye katlar; bu yüzden sonraki yaklaşım, aramaya başlamadan önce birkaç şeyi kontrol eder.

Algoritma

Tahtanın boyutlarında, tüm değerleri false olan bir visited ızgarası oluştur.
dfs(r, c, i) fonksiyonunu tanımla: (r, c) ızgaranın dışındaysa, ziyaret edilmişse veya harfi word[i] değilse false döndür.
i, word'ün son indeksi ise true döndür.
(r, c) hücresini ziyaret edilmiş olarak işaretle, dört komşuyu i+1 ile dene, ardından hücrenin işaretini kaldır ve komşulardan herhangi birinin başarılı olup olmadığını döndür.
Her hücreden dfs(r, c, 0) çağrısı yap ve çağrılardan biri başarılı olur olmaz true döndür.

def exist(board, word):
    rows, cols = len(board), len(board[0])
    visited = [[False] * cols for _ in range(rows)]

    def dfs(r, c, i):
        # Can word[i:] be traced starting at cell (r, c)?
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return False
        if visited[r][c] or board[r][c] != word[i]:
            return False
        if i == len(word) - 1:
            return True
        visited[r][c] = True   # mark: the current path owns this cell
        found = (dfs(r + 1, c, i + 1) or dfs(r - 1, c, i + 1)
                 or dfs(r, c + 1, i + 1) or dfs(r, c - 1, i + 1))
        visited[r][c] = False  # restore: other paths may use it
        return found

    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0):
                return True
    return False

Yerinde işaretleme ve budamayla geri izleme

Sezgi

Aynı aramayı koruyun ve iki değişiklik yapın. İlk olarak, hücreleri ayrı bir ızgara yerine tahtanın özel bir kopyasında işaretleyin: yol hücreyi kullanırken hücrenin üzerine # yazın ve geri dönerken harfi geri yazın. # sözcükteki hiçbir harfe eşit olmadığından, harf kontrolü yoldaki hücreleri de reddeder ve geri yükleme, öncekiyle aynı geri alma adımıdır.

İkinci olarak, aramadan önce budama yapın. Harfleri sayın. Sözcük, tahtada bulunandan daha fazla sayıda bir harfe ihtiyaç duyuyorsa, herhangi bir arama yapmadan yanıt false olur. Böylece, 8 A ve bir B içeren tamamen A'lardan oluşan tahta için yaklaşık 65.000 kontrol yapmak yerine hiç arama yapmadan yanıtı bulursunuz. Daha nadir olan uçtan başlayın. Geriye doğru okunan bir yol, aynı hücrelerde ters çevrilmiş sözcüğü oluşturur; dolayısıyla bunun yerine ters çevrilmiş sözcüğü arayabilirsiniz. Son harf tahtada ilk harften daha nadirse sözcüğü ters çevirin. Aramayı başlatabilecek hücre sayısı azalır ve nadir harf, yanlış başlangıçları son adımda değil ilk adımda eler.

Nadir harf mevcut ama erişilemez olduğunda ikinci kural önem kazanır. Tek B'yi, iki komşusu C olan bir köşeye koyun ve önce 8 A, ardından bir B arayın. Harf sayımı kontrolü geçer. İleri yönde arama, yine de her A yolunu tarar ve yaklaşık 35.000 hücre kontrolü yapar. Ters yönde ise sözcük B ile başlar; yalnızca bir hücre başlangıç olabilir, komşuları A değildir ve arama yaklaşık 30 kontrolün ardından sona erer.

En kötü durum yine O(m·n·3^L) olur: harflerin dengeli dağıldığı ve çıkmazların geç ortaya çıktığı bir tahta ve sözcük oluşturulabilir. Budama yanıtı veya sınırı değiştirmez. Harfleri saymak için gereken tek geçiş karşılığında, düz aramanın zaman kaybetmesine yol açan yaygın durumları ortadan kaldırır ve sözcüğün uzunluğu arttıkça aradaki fark hızla büyür.

Algoritma

Tahtadaki ve kelimedeki her harfi say. Kelime, tahtada bulunandan daha fazla sayıda herhangi bir harf gerektiriyorsa false döndür.
Tahtada word[0] harfinin kopyası, son harften daha fazlaysa word kelimesini tersine çevir.
Tahtayı, değiştirebileceğin bir karakterler ızgarasına kopyala.
dfs(r, c, i) fonksiyonunu tanımla: hücre word[i] değilse başarısız ol; i son indeksse başarılı ol; aksi hâlde hücreyi # olarak ayarla, sınırlar içindeki her komşuyu i+1 ile dene, harfi geri koy ve herhangi birinin başarılı olup olmadığını döndür.
Her hücreden dfs(r, c, 0) çağrısını çalıştır ve biri başarılı olur olmaz true döndür.

from collections import Counter


def exist(board, word):
    rows, cols = len(board), len(board[0])

    # Pruning 1: the board must hold every letter as many times as the word uses it.
    have = Counter("".join(board))
    for letter, need in Counter(word).items():
        if have[letter] < need:
            return False

    # Pruning 2: a path read backwards is the same path, so start from the
    # end whose letter is rarer on the board: fewer cells begin a search.
    if have[word[0]] > have[word[-1]]:
        word = word[::-1]

    grid = [list(row) for row in board]

    def dfs(r, c, i):
        # Can word[i:] be traced starting at cell (r, c)?
        if grid[r][c] != word[i]:
            return False
        if i == len(word) - 1:
            return True
        grid[r][c] = "#"  # mark: "#" matches no letter, so this path cannot reuse the cell
        found = False
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < rows and 0 <= nc < cols and dfs(nr, nc, i + 1):
                found = True
                break
        grid[r][c] = word[i]  # restore the letter for other paths
        return found

    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0):
                return True
    return False

Tuzaklar ve uç durumlar

Yanlış yanıtların çoğu işaretleme ve sınır kontrollerinden kaynaklanır.

Başarısız bir dalın ardından hücrenin işaretini kaldırmamak. Hücre, sonraki tüm yollar için engelli kalır ve AA / AB üzerinde AAA false döner.
Hiç işaretleme yapmamak. İşaretleme olmadan yol, geldiği hücreye geri dönebilir ve örnek tahtada POP true döndürür.
Sınırları kontrol etmeden önce hücreyi okumak. Python'da board[-1] hata değil, son satırdır; bu nedenle eksik bir sınır kontrolü sessizce ızgaranın diğer tarafından devam eder.
Başarıyı yalnızca bir hamleden sonra kontrol etmek. Tek hücreli bir tahtadaki tek harfli bir sözcük, ["A"] ile A, hücrenin komşusu olmasa bile true döndürmelidir.
Gerçek bir harf olabilecek bir karakterle işaretleme yapmak. Örneğin bir hücrenin büyük/küçük harf biçimini değiştirmek, hem a hem de A kullanan tahtalarda soruna yol açar.
Çapraz hareket etmek. Yalnızca bir kenarı paylaşan dört hücre komşu sayılır.

Sıkça sorulan sorular4

Word Search'ün zaman karmaşıklığı nedir?

En kötü durum, m × n boyutunda bir tahta ve L uzunluğunda bir sözcük için O(m·n·3^L) şeklindedir. m·n hücrenin her biri bir yol başlatabilir ve ilk adımdan sonra her hücrenin denenebilecek en fazla üç ziyaret edilmemiş komşusu vardır. Ek alan, özyineleme için O(L), ayrıca tahtayı işaretlemek için kopyalarsanız O(m·n) olur.

Kelime Bulmaca'da hücrelerin işaretini neden kaldırıyorsunuz?

Bir işaret, hücrenin mevcut yol üzerinde olduğu anlamına gelir. Bir dal başarısız olduğunda hücre yoldan çıkar ve başka bir yolun ona ihtiyacı olabilir. İşareti korursan sonraki aramalar hücreyi kullanılmış sayar ve geçerli bir izlemeyi kaçırabilir. Girerken işaretle, çıkarken işareti kaldır.

Budama, Word Search'ü nasıl hızlandırır?

Aramadan önce iki kontrol yapılır. Kelime, tahtada bulunandan daha fazla sayıda bir harf gerektiriyorsa arama yapmadan false döndürebilirsin. Ayrıca, bir yol tersten okunduğunda kelimenin tersten yazılışını verdiği için, daha seyrek bulunan harfin olduğu uçtan başlayabilirsin; böylece başlangıç hücrelerinin sayısı azalır ve yanlış yollar daha erken elenir. Bu kontroller en kötü durum performansını değiştirmez ve basit arama tek başına da eksiksiz bir çözümdür. A harflerinden oluşan 5 × 5'lik bir tahtada, eksik bir B gerektiren bir kelime için yaklaşık 65.000 hücre kontrolünü sıfıra indirirler.

Word Search ile Word Search II arasındaki fark nedir?

Word Search tek bir kelime hakkında soru sorar. Word Search II bir kelime listesi verir ve bunlardan hangilerinin tahtada bulunduğunu sorar. Bu aramayı her kelime için bir kez çalıştırmak çok fazla işi tekrarlar; bu nedenle yaygın çözüm, tüm kelimeleri bir trie içine yerleştirir ve tahtayı bir kez dolaşarak harfleriyle başlayan hiçbir kelime kalmadığında yolu terk eder.

Python

def exist(board, word):
    # Kodu buraya yazın

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

board = ["STAR", "POOL", "ENDS"]
word = "STOOLS"

Beklenen

true