# A non-recursive solution, but slow

• ``````class Solution(object):
def exist(self, board, word):
"""
:type board: List[List[str]]
:type word: str
:rtype: bool
"""
if word == "": return True
s, use = [], []
Y, X = len(board), len(board[0])
if len(word) > Y * X: return False
for y in range(Y):
use.append([False] * X)
for y in range(Y):
for x in range(X):
if board[y][x] == word[0]:
s.append(((y, x), 0))
s.append(((y, x), word[1:]))
while s:
(y, x), word = s.pop()
if word == "":
return True
if word == 0:
use[y][x] = False
else:
use[y][x] = True
for ny, nx in ((y + 1, x), (y - 1, x), (y, x + 1), (y, x - 1)):
if 0 <= nx < X and 0 <= ny < Y and board[ny][nx] == head and not use[ny][nx]:
s.append(((ny, nx), 0))
s.append(((ny, nx), word[1:]))
return False
``````

Notice that when I push items into the stack, I pushed it twice, so when the first one gets popped, I start to visit its children; when the second one gets popped, I know that all its children have been dealt with. `use` matrix is not necessary as we can modify the board in-place. The way I did it was with `ord` and `chr` functions to convert betwwen char and its numeric representation. One can also wrap the char in a tuple or something to mark the difference here.

This solution is not fast, but it's space efficient due to the elimation of recursive calls.

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