Word Search

Problem

Return True if word can be traced through a grid of characters by moving between horizontally or vertically adjacent cells without reusing a cell.

Run DFS from every starting cell, temporarily marking visited cells and restoring them on backtracking. An empty word is trivially found.

Hint

Mark the current cell before recursing so the same cell cannot be counted twice, then unmark it.

case 1

in: [[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]],"ABCCED"]

expected: true

case 2

in: [[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]],"SEE"]

expected: true

case 3

in: [[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]],"ABCB"]

expected: false

case 4

in: [[["a"]],"a"]

expected: true

case 5

in: [[["a"]],"b"]

expected: false

case 6

in: [[[]],""]

expected: true

Starter codePython

def word_search(board, word):
    # Your code here
    pass

6 test cases · run your code against them in the editor