Word Search

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

O(m·n·3^L) für ein m × n -Spielfeld und ein Wort der Länge L : Jede Zelle kann einen Pfad beginnen, und nach dem ersten Schritt hat jede Zelle höchstens drei unbesuchte Nachbarn. Der zusätzliche Speicherplatz beträgt O(L) für die Rekursion sowie O(m·n) für eine Kopie des Spielfelds.

MittelBacktracking Graphen

+10

Du erhältst ein Buchstabenraster board, eine 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 nachverfolgen kannst: Beginne auf einem beliebigen Feld und gehe jedes Mal zum Feld darüber, darunter, links oder rechts davon, sodass die besuchten Felder word der Reihe nach ergeben, ohne ein Feld zweimal zu verwenden. Andernfalls gib false zurück. Bei Buchstaben wird zwischen Groß- und Kleinschreibung unterschieden.

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 oben links bei S, gehe nach rechts zu T, nach unten zu O, nach rechts zu O und L und nach unten zum S unter dem L. Keine Zelle wird wiederholt.

Eingabe: board = ["STAR", "POOL", "ENDS"]word = "POP"
Ausgabe: false
Erklärung: Das Spielfeld hat ein P. Nach P und O brauchst du ein weiteres P, und das einzige ist das Startfeld, 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 das einzige A in Zeile 0, Spalte 2 berührt kein S.

Weiterführende Frage

Kannst du statt mit Ja oder Nein zu antworten zählen, wie viele verschiedene Wege für word das Spielfeld enthält?

Tipps

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

0 von 3 geöffnet

Lösung

Du musst die Pfade durch das Raster suchen. Beim Backtracking wird ein Pfad Buchstabe für Buchstabe erweitert, wobei jedes Feld markiert wird, solange der Pfad es enthält, und beim Zurückgehen wieder entmarkiert wird, damit kein Pfad ein Feld erneut verwendet. Die Suche wächst exponentiell mit der Länge des Wortes, was ein 6 × 6-Brett ermöglicht.

Backtracking mit einem besuchten Raster

Idee

Ein Pfad, der die ersten i Buchstaben enthält, wird zu jedem Nachbarn fortgesetzt, der word[i] enthält und nicht auf dem Pfad liegt. Gibt es keinen solchen Nachbarn, ist der Pfad eine Sackgasse, und du gehst zurück.

Das Zurücksetzen der Markierung sorgt dafür, dass dies korrekt ist: Eine Zelle, über die eine Sackgasse geführt hat, muss für den nächsten Versuch frei sein. Bei AA / AB mit AAA bleiben beide Versuche von oben links stecken. Wenn ihre Zellen markiert blieben, würde die Antwort – unten links, dann oben links, dann oben rechts – übersehen.

Nach dem ersten Zug gibt es bei jedem Schritt höchstens drei neue Richtungen, sodass die Suche bis zu m·n·3^L Pfade erkunden kann. Auf einem 5 × 5 großen Brett mit As, 8 As und danach einem B prüft sie etwa 53.000 Zellen, bevor sie mit false antwortet.

Algorithmus

Erstelle ein visited-Raster, das überall false ist.
dfs(r, c, i): false, wenn (r, c) außerhalb des Rasters liegt, besucht wurde oder nicht word[i] entspricht; true, wenn i der letzte Index ist.
Markiere andernfalls (r, c), probiere die vier Nachbarzellen mit i+1 aus, hebe die Markierung wieder auf und gib zurück, ob einer der Versuche erfolgreich war.
Gib true zurück, wenn dfs(r, c, 0) von irgendeiner Zelle aus 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 am Ort und Beschneidung

Idee

Behalte die Suche bei, mit zwei Änderungen. Markiere Zellen auf einer Kopie des Spielfelds, indem du # einträgst, und stelle den Buchstaben auf dem Rückweg wieder her. # stimmt nie mit einem Buchstaben des Wortes überein, daher weist die Buchstabenprüfung auch Zellen auf dem Pfad zurück.

Führe anschließend ein Pruning durch. Wenn das Wort von einem Buchstaben mehr Vorkommen benötigt, als auf dem Spielfeld vorhanden sind, gib false zurück: Damit wird das Spielfeld gelöst, das nur aus A besteht, ohne eine Suche durchzuführen. Ein rückwärts gelesener Pfad ergibt auf denselben Zellen das umgekehrte Wort, daher liefert die Suche nach dem umgekehrten Wort dieselbe Antwort. Beginne an dem Ende, dessen Buchstabe auf dem Spielfeld seltener ist: Es kommen weniger Zellen als Startpunkte infrage, und falsche Startpunkte scheitern sofort.

Wenn das einzige B in einer Ecke zwischen zwei Cs liegt, führt die Suche vorwärts etwa 35.000 Zellenprüfungen durch; rückwärts sind es 27. Der schlechteste Fall bleibt O(m·n·3^L).

Algorithmus

Wenn das Wort mehr Vorkommen eines Buchstabens benötigt, als das Spielfeld enthält, gib false zurück.
Wenn das Spielfeld mehr Vorkommen von word[0] als vom letzten Buchstaben enthält, kehre word um.
Kopiere das Spielfeld in ein Raster, das du ändern kannst.
dfs(r, c, i): Schlägt fehl, wenn die Zelle nicht word[i] ist; ist am letzten Index erfolgreich; setze sie andernfalls auf #, probiere jeden benachbarten Eintrag innerhalb der Grenzen mit i+1 aus, stelle den ursprünglichen Wert wieder her und gib zurück, ob einer erfolgreich war.
Gib true zurück, wenn dfs von einer beliebigen Zelle aus 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

Eine Zelle nach einem fehlgeschlagenen Zweig nicht wieder freigeben: AAA mit AA / AB ergibt false.
Gar nichts markieren: Der Pfad geht einen Schritt zurück auf seine letzte Zelle, und POP gibt auf dem Beispielbrett true zurück.
Die Zelle lesen, bevor die Grenzen geprüft werden: In Python ist board[-1] die letzte Zeile, sodass sich Pfade im Raster am Rand fortsetzen.
Erst nach einem Zug auf Erfolg prüfen: ["A"] mit A muss true zurückgeben.
Eine Zelle markieren, indem ihre Groß- und Kleinschreibung geändert wird: Auf ["aA"] wird das markierte a als zweites A gelesen, sodass aAA true ergibt.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität von Word Search?

O(m·n·3^L) für ein m × n-Spielfeld und ein Wort der Länge L: Jede Zelle kann einen Pfad beginnen, und nach dem ersten Schritt hat jede Zelle höchstens drei unbesuchte Nachbarn. Der zusätzliche Speicherplatz beträgt O(L) für die Rekursion sowie O(m·n) für eine Kopie des Spielfelds.

Wie beschleunigt Pruning die Wortsuchsuche?

Zähle zuerst die Buchstaben und gib false zurück, wenn das Brett zu wenige von einem davon enthält. Suche dann vom Ende aus mit dem selteneren Buchstaben, mit dem weniger Zellen beginnen können. Keine der beiden Prüfungen ändert den Worst Case.

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

Word Search II fragt, welche Wörter aus einer Liste auf dem Spielbrett vorkommen. Für jedes Wort einzeln zu suchen, wiederholt Arbeit. Daher speichert die übliche Lösung die Wörter in einem Trie und durchläuft das Spielbrett einmal. Dabei wird ein Pfad abgebrochen, wenn kein Wort mit seinen Buchstaben beginnt.

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

Test #1

Test #2

Test #3

Argumente

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

Erwartete Ausgabe

true