Word Search

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

m × n boyutlarında bir tahta ve uzunluğu L olan bir sözcük için O(m·n·3^L) : her hücre bir yol başlatabilir ve ilk adımdan sonra her hücrenin en fazla üç ziyaret edilmemiş komşusu vardır. Ek alan, özyineleme için O(L) ve tahtanın bir kopyası için O(m·n) kadardır.

OrtaGeri izleme Graflar

+10

Bir harf ızgarası board, board[r][c] değerinin r satırındaki, c sütunundaki harf olduğu bir dizge listesi ve bir word dizgesi veriliyor.

word dizgesinin izini sürebiliyorsan true döndür: herhangi bir hücreden başla ve her adımda üstündeki, altındaki, solundaki veya sağındaki hücreye geç; böylece ziyaret ettiğin hücreler sırayla word dizgesini oluşturmalı ve hiçbir hücreyi iki kez kullanmamalısın. Aksi takdirde false döndür. Harflerde büyük-küçük harf duyarlılığı vardı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 kelime
Döndürürboolean: kelimenin, her biri en fazla bir kez kullanılacak şekilde yan yana hücreler boyunca izlenip izlenemeyeceği

Kısıtlar

1 ≤ board.length ≤ 6
1 ≤ board[i].length ≤ 6 ve her satır aynı uzunluğa sahiptir.
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: Sol üstteki S noktasından başlayın, sağa T noktasına gidin, aşağı O noktasına, sağa O ve L noktalarına, ardından aşağı, L harfinin altındaki S noktasına gidin. Hiçbir hücre tekrarlanmaz.

Girdi: board = ["STAR", "POOL", "ENDS"]word = "POP"
Çıktı: false
Açıklama: Tahtada bir tane P var. P ve O'dan sonra başka bir P'ye ihtiyacın var, ancak tek olan başlangıç hücresidir ve iki kez kullanılamaz.

Girdi: board = ["STAR", "POOL", "ENDS"]word = "SAND"
Çıktı: false
Açıklama: SAND harflerinin tümü tahtada, ancak 0. satır, 2. sütundaki tek A, hiçbir S'ye değmiyor.

Ek soru

Evet ya da hayır demek yerine, tahtada word sözcüğünün kaç farklı izini bulabileceğini sayabilir misin?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Izgaradaki yolları aramanız gerekir. Geri izleme, her seferinde bir harf ekleyerek bir yol oluşturur; yol o hücreyi kullandığı sürece her hücreyi işaretler ve geri dönerken işareti kaldırır, böylece hiçbir yol aynı hücreyi yeniden kullanmaz. Arama, sözcüğün uzunluğuna göre üstel karmaşıklıktadır; 6 × 6'lık bir tahta bunu mümkün kılar.

Ziyaret edilmiş bir ızgarayla geri izleme

Sezgi

İlk i harfi eşleşen bir yol, word[i] harfini içeren ve yol üzerinde olmayan herhangi bir komşu hücreye devam eder. Böyle bir komşu yoksa çıkmaz sokağa ulaşır ve geri dönersin.

İşareti kaldırmak, bunun doğru çalışmasını sağlar: çıkmaz sokağın üzerinden geçtiği bir hücre, sonraki deneme için boş olmalıdır. AA / AB tahtasında AAA aranırken sol üstten yapılan iki deneme de takılır. Hücreleri işaretli kalsaydı, sol alttan başlayıp sonra sol üstten ve ardından sağ üstten geçen yanıt bulunamazdı.

İlk hamleden sonra her adımda en fazla üç yeni yön olduğundan, arama en fazla m·n·3^L yolu inceleyebilir. 8 tane A ve ardından bir B içeren 5 × 5 boyutunda, A harflerinden oluşan bir tahtada, false yanıtını vermeden önce yaklaşık 53.000 hücre kontrolü yapar.

Algoritma

Tüm değerleri false olan bir visited ızgarası oluştur.
dfs(r, c, i): (r, c) ızgaranın dışındaysa, ziyaret edilmişse veya word[i] değilse false döndür; i son indeksse true döndür.
Aksi hâlde (r, c) hücresini işaretle, i+1 ile dört komşuyu dene, işareti kaldır ve denemelerden herhangi birinin başarılı olup olmadığını döndür.
Herhangi bir hücreden dfs(r, c, 0) başarılı olursa 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

Aramayı sürdür, iki değişiklik yap. Tahtanın bir kopyasında hücreleri # yazarak işaretle ve geri dönerken harfi eski hâline getir. # sözcükteki hiçbir harfle eşleşmediğinden, harf kontrolü yoldaki hücreleri de eler.

Ardından budama yap. Sözcükte tahtadakinden daha fazla sayıda bir harf gerekiyorsa false döndür: böylece arama yapmadan tümü A olan tahtadaki durumu yanıtlamış olursun. Bir yol tersten okunduğunda aynı hücrelerde ters çevrilmiş sözcüğü oluşturur; dolayısıyla ters çevrilmiş sözcüğü aramak aynı yanıtı verir. Tahtada daha seyrek bulunan harfin olduğu uçtan başla: daha az hücre başlangıç olabilir ve yanlış başlangıçlar hemen elenir.

İki C arasında bir köşede bulunan tek B ile ileri yöndeki arama yaklaşık 35.000 hücre kontrolü yapar; ters yönde ise 27. En kötü durum yine O(m·n·3^L) olarak kalır.

Algoritma

Herhangi bir harften, word içinde board'da bulunandan daha fazla gerekiyorsa false döndür.
board'da word[0] harfinden, son harften daha fazla kopya varsa word'ü tersine çevir.
board'u değiştirebileceğin bir ızgaraya kopyala.
dfs(r, c, i): hücre word[i] değilse başarısız ol; son indeksteyse başarılı ol; aksi hâlde onu # olarak ayarla, sınırlar içindeki her komşuyu i+1 ile dene, hücreyi eski hâline getir ve herhangi bir denemenin başarılı olup olmadığını döndür.
dfs herhangi bir hücreden başarılı olursa 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

Başarısız bir dalın ardından hücrenin işaretini kaldırmamak: AA / AB üzerinde AAA false döner.
Hiç işaretlememek: yol son hücresine geri adım atar ve POP, örnek tahtada true döner.
Sınırları kontrol etmeden önce hücreyi okumak: Python'da board[-1] son satırdır, bu nedenle yollar ızgarada dolanır.
Başarıyı yalnızca bir hamleden sonra kontrol etmek: A ile ["A"] true döndürmelidir.
Bir hücrenin büyük/küçük harf durumunu değiştirerek işaretlemek: ["aA"] üzerinde, işaretlenmiş a ikinci bir A olarak okunur, bu nedenle aAA true döner.

Sıkça sorulan sorular3

Word Search algoritmasının zaman karmaşıklığı nedir?

m × n boyutlarında bir tahta ve uzunluğu L olan bir sözcük için O(m·n·3^L): her hücre bir yol başlatabilir ve ilk adımdan sonra her hücrenin en fazla üç ziyaret edilmemiş komşusu vardır. Ek alan, özyineleme için O(L) ve tahtanın bir kopyası için O(m·n) kadardır.

Budama, Kelime Arama'yı nasıl hızlandırır?

Önce harfleri sayın ve tahtada harflerden biri yeterince yoksa false döndürün. Ardından, daha az hücrenin başlangıç noktası olabildiği daha nadir harfle sondan başlayarak arama yapın. Bu kontrollerin hiçbiri en kötü durumu değiştirmez.

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

Word Search II, listedeki hangi sözcüklerin tahtada bulunduğunu sorar. Her sözcük için bir kez arama yapmak aynı işi tekrarlar; bu yüzden yaygın çözüm, sözcükleri bir trie'ye yerleştirip tahtayı bir kez dolaşmak ve harfleriyle başlayan hiçbir sözcük yoksa yolu bırakmaktır.

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

Test #1

Test #2

Test #3

Argümanlar

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

Beklenen Çıktı

true