# 106 ms python solution

• class Solution(object):

``````# The solution is:
# First of all, check the length of the word
# if the length of the word > size of the board. Board impossible contains the word
# after that, checking whether the borad contains the possible solution. check function is designed for that
# then use the DSP to find a solution
# dsp contains for different move. there are: go up, go down, go left, and go right.
# when you do your move, first of all, make sure next move is in bound
# To avoid repeat Selection. once you make a move. mark that space. I use the " "
# sometimes, you move don't have a solution. e.g, you go right first, but after traversal,
# right doesn't have a solution. Then, you will check another direction
# in this situation, remember reset the original space. when you
# go other direction, you don't want right space have your marking
# when you find a solution, return True. no solution return False

def check(self,board,word):
# buf store all elements of the board
# ind store all elemts of the word
buf = []
ind = []

for i in word:
buf.append(i)

for row in range(len(board)):

for column in range(len(board[0])):

# print board[row][column]
ind.append(board[row][column])
i = 0
# check whether board contains a possible solution
while i in range(len(buf)):

if buf[i] in ind:
ind.remove(buf[i])
buf.remove(buf[i])
else:
return False

if not buf:
return True
else:
return False

def dfs(self,board, word, row, column):

# first store the original value
# if one direction no solution
# reset the space and check the other direction
first = word[0]
word = word[1:]

if len(word) == 0:
return True

board[row][column] = " "
row_next = row + 1
row_last = row - 1
column_next = column + 1
column_last = column - 1

# go right
if column_next <= len(board[0]) - 1:
if word[0] == board[row][column_next]:
if self.dfs(board,word,row,column_next):
return True
# go down
if row_next <= len(board) - 1:
if word[0] == board[row_next][column]:
if self.dfs(board,word,row_next,column):
return True
# go up
if row_last >= 0:
if word[0] == board[row_last][column]:
if self.dfs(board,word,row_last,column):
return True
# go left
if column_last >= 0:
if word[0] == board[row][column_last]:
if self.dfs(board,word,row,column_last):
return True

board[row][column] = first

return False

def exist(self,board, word):

if not word:

return True

if not board:

return False

if len(word) > len(board) * len(board[0]):
return False

if self.check(board , word) == False:
return False

for row in range(len(board)):

for column in range(len(board[0])):

if board[row][column] == word[0]:

if self.dfs(board,word,row,column):
return True

return False``````

• if you have a issue about my code. you can leave your question or email me. I'm happy to reply your issue

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