Word Search

Q: Wie hoch ist die Zeitkomplexität von Word Search?

Der schlechteste Fall ist O(m·n·3^L) für ein m × n -Spielfeld und ein Wort der Länge L . Jede der m·n -Zellen kann einen Pfad beginnen, und nach dem ersten Schritt hat jede Zelle höchstens drei unbesuchte Nachbarn, die ausprobiert werden können. Der zusätzliche Speicherbedarf beträgt O(L) für die Rekursion, zuzüglich O(m·n) , wenn du das Spielfeld kopierst, um Zellen zu markieren.

MittelBacktracking Graphen

+10

Du erhältst ein Buchstabengitter board, dargestellt als Liste von Zeichenfolgen, wobei board[r][c] der Buchstabe in Zeile r, Spalte c ist, sowie eine Zeichenfolge word.

Gib true zurück, wenn du word im Gitter nachverfolgen kannst: Beginne in einer beliebigen Zelle und gehe bei jedem Schritt zu der Zelle direkt über, unter, links oder rechts von der aktuellen Zelle, sodass die besuchten Zellen word der Reihe nach ergeben. Eine Nachverfolgung darf dieselbe Zelle nicht zweimal verwenden. Andernfalls gib false zurück. Bei Buchstaben wird zwischen Groß- und Kleinschreibung unterschieden, daher sind a und A unterschiedlich.

Funktion

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

boardstring-array: das Raster, eine Buchstabenfolge pro Zeile
wordstring: das Wort zum Nachzeichnen
Gibt zurückboolean: ob sich ein Wort durch nebeneinanderliegende Zellen verfolgen lässt, wobei jede höchstens einmal verwendet wird

Einschränkungen

1 ≤ board.length ≤ 6
1 ≤ board[i].length ≤ 6, und jede Zeile hat dieselbe Länge.
1 ≤ word.length ≤ 20
board und word enthalten nur englische Buchstaben, Groß- und Kleinbuchstaben.

Beispiele

Eingabe: board = ["STAR", "POOL", "ENDS"]word = "STOOLS"
Ausgabe: true
Erklärung: Beginne beim S in Zeile 0, Spalte 0, gehe dann nach rechts zu T, nach unten zu O, nach rechts zum zweiten O, nach rechts zu L und nach unten zum S in Zeile 2, Spalte 3. Das sind sechs verschiedene Zellen, von denen jede neben der vorherigen liegt.

Eingabe: board = ["STAR", "POOL", "ENDS"]word = "POP"
Ausgabe: false
Erklärung: Das Spielbrett enthält ein einzelnes P in Zeile 1, Spalte 0. Nach P und O brauchst du ein weiteres P, und das einzige befindet sich auf dem Feld, auf dem der Pfad begonnen hat und das nicht zweimal verwendet werden kann.

Eingabe: board = ["STAR", "POOL", "ENDS"]word = "SAND"
Ausgabe: false
Erklärung: Jeder Buchstabe von SAND befindet sich auf dem Spielbrett, aber der Pfad bricht bereits beim ersten Schritt ab: Das einzige A befindet sich in Zeile 0, Spalte 2, und keines der beiden S grenzt daran.

+23 versteckte Tests beim Einreichen

Weiterführende Frage

Kannst du statt mit Ja oder Nein zu antworten zählen, wie viele verschiedene Wege für word es auf dem Brett gibt?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Keine Formel beantwortet diese Frage: Du musst die Pfade durch das Raster durchsuchen. Backtracking erledigt das jeweils mit einem Pfad. Du verlängerst den Pfad um einen Buchstaben, markierst jede Zelle, solange der Pfad sie belegt, und hebst die Markierung wieder auf, wenn du zurückgehst. So wird eine Zelle innerhalb eines Pfads nie wiederverwendet, bleibt aber für alle anderen Pfade frei. Diese Suche ist im schlechtesten Fall exponentiell in der Länge des Wortes, was bei einem Spielfeld mit höchstens 6 × 6 Zellen in Ordnung ist. Zwei einfache Prüfungen davor – das Zählen der Buchstaben und der Start am selteneren Ende des Wortes – reduzieren den Aufwand oft von Zehntausenden Schritten auf einige Dutzend.

Backtracking mit einem besuchten Raster

Idee

Stell dir einen Entscheidungsbaum vor. Die erste Wahl ist die Startzelle, und sie muss word[0] enthalten. Danach steht jeder Knoten für einen Pfad, der die ersten i Buchstaben schreibt, und seine Kinder sind die Nachbarzellen, die word[i] enthalten und noch nicht auf dem Pfad liegen. Ein Pfad, der das ganze Wort schreibt, ist ein Erfolg. Ein Pfad ohne einen solchen Nachbarn ist eine Sackgasse, und du gehst zurück, um die nächste Möglichkeit auszuprobieren.

Ein visited-Raster setzt die Regel um, dass jede Zelle nur einmal verwendet werden darf. Markiere eine Zelle, wenn der Pfad sie betritt, und entferne die Markierung, wenn der Pfad sie wieder verlässt. Dieses Entfernen der Markierung macht das Ganze zu Backtracking: Eine Zelle, über die ein Pfad in eine Sackgasse geführt hat, muss für den nächsten Versuch wieder frei sein. Auf dem Brett AA / AB mit dem Wort AAA bleibt der Start oben links stecken, wenn du nach unten gehst: Die andere Nachbarzelle unten links enthält B. Wenn du nach rechts gehst, bleibt der Pfad oben rechts stecken. Blieben diese Zellen markiert, könnte die Antwort – unten links, dann oben links, dann oben rechts – niemals gefunden werden.

Das ist die Standardlösung, und sie ist hier korrekt und schnell genug. Ihre Laufzeit hängt von der Anzahl der Pfade ab, die sie untersucht. Nach dem ersten Schritt gibt es bei jedem Schritt höchstens drei neue Richtungen, daher kann ein Wort mit L Buchstaben in der Größenordnung von m·n·3^L Pfaden bedeuten. Nimm ein 5 × 5 großes Brett voller A und das Wort aus 8 As, gefolgt von einem B. Jeder Pfad aus As ist ein gültiges Präfix, und die Suche durchläuft sie alle, bevor sie herausfindet, dass es kein B gibt: etwa 65.000 Zellprüfungen, um mit false zu antworten. Jeder zusätzliche Buchstabe verdoppelt diese Anzahl ungefähr. Deshalb prüft der nächste Ansatz vor der Suche einige Dinge.

Algorithmus

Erstelle ein visited-Raster in der Größe des Spielbretts, in dem alle Werte false sind.
Definiere dfs(r, c, i): Gib false zurück, wenn (r, c) außerhalb des Rasters liegt, besucht wurde oder sein Buchstabe nicht word[i] ist.
Wenn i der letzte Index von word ist, gib true zurück.
Markiere (r, c) als besucht, probiere die vier Nachbarzellen mit i+1 aus, hebe dann die Markierung wieder auf und gib zurück, ob einer der Nachbarn erfolgreich war.
Rufe dfs(r, c, 0) von jeder Zelle aus auf und gib true zurück, sobald ein Aufruf erfolgreich ist.

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

Backtracking mit Markierungen direkt vor Ort und Beschneidung

Idee

Behalte dieselbe Suche bei und nimm zwei Änderungen vor. Markiere zuerst die Zellen auf einer privaten Kopie des Spielfelds statt in einem separaten Raster: Überschreibe eine Zelle mit #, solange der Pfad sie belegt, und schreibe den Buchstaben zurück, wenn du zurückgehst. # ist nie gleich einem Buchstaben des Wortes, daher weist der Buchstabenvergleich auch Zellen auf dem Pfad zurück, und das Wiederherstellen ist derselbe Rückgängigmachungsschritt wie zuvor.

Als Zweites: Beschneide den Suchraum, bevor du mit der Suche beginnst. Zähle die Buchstaben. Wenn das Wort mehr Vorkommen eines Buchstabens benötigt, als das Spielfeld enthält, lautet die Antwort false, ohne dass überhaupt gesucht werden muss. Damit lässt sich das Spielfeld mit lauter As, nämlich 8 As, und einem B ohne jede Suche beantworten statt mit etwa 65.000 Prüfungen. Beginne am selteneren Ende. Ein rückwärts gelesener Pfad ergibt auf denselben Zellen das umgekehrte Wort, du kannst also stattdessen nach dem umgekehrten Wort suchen. Wenn der letzte Buchstabe auf dem Spielfeld seltener ist als der erste, kehre das Wort um. So können weniger Zellen eine Suche beginnen, und der seltene Buchstabe schließt falsche Startpunkte gleich beim ersten Schritt statt erst beim letzten aus.

Die zweite Regel ist wichtig, wenn der seltene Buchstabe zwar vorkommt, aber unerreichbar ist. Platziere das einzige B in einer Ecke, deren zwei Nachbarn C sind, und suche nach 8 As und anschließend einem B. Die Buchstabenzählung ist erfolgreich. Vorwärts durchläuft die Suche weiterhin jeden A-Pfad, also etwa 35.000 Zellprüfungen. Umgekehrt beginnt das Wort mit B; nur eine Zelle kann den Start bilden, ihre Nachbarn sind keine As, und die Suche endet nach etwa 30 Prüfungen.

Der schlechteste Fall bleibt O(m·n·3^L): Es lässt sich ein Spielfeld und ein Wort konstruieren, bei denen die Buchstaben gleichmäßig verteilt sind und die Sackgassen erst spät auftreten. Das Beschneiden ändert weder die Antwort noch die Schranke. Es beseitigt die üblichen Ursachen dafür, dass die einfache Suche Zeit verschwendet, und erfordert dafür nur einen Durchlauf zum Zählen der Buchstaben; mit zunehmender Wortlänge wächst der Unterschied schnell.

Algorithmus

Zähle jeden Buchstaben auf dem Brett und im Wort. Wenn das Wort mehr von einem Buchstaben benötigt, als auf dem Brett vorhanden sind, gib false zurück.
Wenn das Brett mehr Vorkommen von word[0] als vom letzten Buchstaben enthält, kehre word um.
Kopiere das Brett in ein Raster aus Zeichen, die du ändern kannst.
Definiere dfs(r, c, i): Schlägt fehl, wenn die Zelle nicht word[i] ist; ist erfolgreich, wenn i der letzte Index ist; andernfalls setze die Zelle auf #, probiere jeden gültigen benachbarten Eintrag mit i+1 aus, setze den Buchstaben zurück und gib zurück, ob einer erfolgreich war.
Führe dfs(r, c, 0) von jeder Zelle aus und gib true zurück, sobald ein Aufruf erfolgreich ist.

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

Stolperfallen und Grenzfälle

Die meisten falschen Antworten entstehen durch das Markieren und die Grenzprüfungen.

Eine Zelle nach einem fehlgeschlagenen Zweig nicht wieder freizugeben. Die Zelle bleibt für alle späteren Pfade blockiert, und bei AA / AB ergibt das Wort AAA false.
Überhaupt nichts zu markieren. Ohne Markierung kann der Pfad wieder auf die Zelle zurückgehen, von der er gekommen ist, und POP würde auf dem Beispielbrett true zurückgeben.
Die Zelle auszulesen, bevor die Grenzen geprüft werden. In Python ist board[-1] die letzte Zeile und kein Fehler. Ohne Grenzprüfung läuft das Raster also unbemerkt am Rand weiter.
Den Erfolg erst nach einem Zug zu prüfen. Ein Wort mit einem Buchstaben auf einem Brett mit einer Zelle, ["A"] mit A, muss true zurückgeben, obwohl die Zelle keine Nachbarn hat.
Mit einem Zeichen zu markieren, das auch ein echter Buchstabe sein kann. Die Groß- und Kleinschreibung einer Zelle zu ändern, funktioniert zum Beispiel nicht auf Brettern, auf denen sowohl a als auch A vorkommen.
Diagonal zu gehen. Nur die vier Zellen, die eine Seite gemeinsam haben, zählen als Nachbarn.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität von Word Search?

Der schlechteste Fall ist O(m·n·3^L) für ein m × n-Spielfeld und ein Wort der Länge L. Jede der m·n-Zellen kann einen Pfad beginnen, und nach dem ersten Schritt hat jede Zelle höchstens drei unbesuchte Nachbarn, die ausprobiert werden können. Der zusätzliche Speicherbedarf beträgt O(L) für die Rekursion, zuzüglich O(m·n), wenn du das Spielfeld kopierst, um Zellen zu markieren.

Warum hebst du die Markierung von Zellen in der Wortsuchaufgabe auf?

Eine Markierung bedeutet, dass sich die Zelle auf dem aktuellen Pfad befindet. Wenn ein Zweig scheitert, verlässt die Zelle den Pfad, und ein anderer Pfad benötigt sie möglicherweise. Wenn du die Markierung beibehältst, behandeln spätere Suchen die Zelle als verwendet und übersehen möglicherweise eine gültige Spur. Markiere beim Betreten und entferne die Markierung beim Verlassen.

Wie macht Pruning die Wortsuchfunktion schneller?

Vor der Suche werden zwei Prüfungen durchgeführt. Wenn das Wort mehr Vorkommen eines Buchstabens benötigt, als das Brett enthält, kannst du ohne Suche false zurückgeben. Und da ein rückwärts gelesener Pfad das umgekehrte Wort ergibt, kannst du an dem Ende beginnen, an dem der Buchstabe seltener ist. Dadurch verringert sich die Anzahl der Startzellen, und falsche Pfade scheitern früher. Beides ändert nichts am Worst Case, und die einfache Suche ist für sich genommen bereits eine vollständige Lösung. Auf einem 5 × 5-Brett mit A machen sie aus ungefähr 65.000 Zellenprüfungen gar keine.

Was ist der Unterschied zwischen Word Search und Word Search II?

Word Search sucht nach einem Wort. Word Search II erhält eine Liste von Wörtern und fragt, welche davon auf dem Spielfeld vorkommen. Diese Suche für jedes Wort einzeln auszuführen, wiederholt viele Arbeitsschritte. Daher fügt die übliche Lösung alle Wörter in einen Trie ein und durchläuft das Spielfeld einmal. Dabei wird ein Pfad abgebrochen, sobald kein Wort mit den entsprechenden Buchstaben beginnt.

Python

def exist(board, word):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

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

Erwartet

true