# Python, Backtracking, DFS easy to read solution. Includes complexity explanation

• class Solution(object):
def dfs(self, board, word, x, y, start):
if start == len(word):
return False
if board[x][y] != word[start] or board[x][y] == -1:
return False
if start == len(word) - 1:
return True

# mark visited, otherwise you can loop the characters
tmp = board[x][y]
board[x][y] = -1
for i in range(4):
xx = x + self.x_dirs[i]
yy = y + self.y_dirs[i]
if 0 <= xx < self.w and 0 <= yy < self.h:
if self.dfs(board, word, xx, yy, start + 1):
return True
board[x][y] = tmp
return False

def exist(self, board, word):
"""
:type board: List[List[str]]
:type word: str
:rtype: bool
"""
if not board:
return False

self.x_dirs = [-1, 0, 1, 0]
self.y_dirs = [0, 1, 0, -1]
self.w = len(board)
self.h = len(board[0])

for x in range(self.w):
for y in range(self.h):
if self.dfs(board, word, x, y, 0):
return True
return False

The time complexity of this algorithm is O(nm^2) where n and m are the height and widths of the board. There is a square because per element in the board we are doing a search that can be 4^(length_of_word) where 4^(length_of_word) == m*n in the worst case. (The 4 is there because we go in 4 directions recursively per character in the word)

The average case time complexity would be O(n * m * 4^(length_of_word).

The space complexity is constant because instead of a visited map we do in-place board mutations :)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.