```
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
head = word[0]
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.