Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
Example:
board = [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ]
Given word = "ABCCED", return true. Given word = "SEE", return true. Given word = "ABCB", return false.
My code:
class Solution:
def exist(self, board, word):
"""
:type board: List[List[str]]
:type word: str
:rtype: bool
"""
m=len(board)
if m==0:
return False
example=board[0]
if len(example)==0:
return False
n=len(example)
self.m=m
self.n=n
self.length=len(word)
for i in range(self.m):
for j in range(self.n):
label=self.check(board,i,j,word)
if label:
return True
return False
def check(self,board,i,j,word):
if len(word)>0 and (i==self.m or j==self.n):
return False
if len(word)>0 and (i<0 or j<0):
return False
if len(word)==1:
if board[i][j]==word[0]:
return True
else:
return False
if len(word)==0:
return True
if board[i][j]==word[0]:
tmp_change=board[i][j]
board[i][j]='0'
label1=self.check(board,i+1,j,word[1:])
if label1:
return True
label1=self.check(board,i-1,j,word[1:])
if label1:
return True
label1=self.check(board,i,j+1,word[1:])
if label1:
return True
label1=self.check(board,i,j-1,word[1:])
if label1:
return True
board[i][j]=tmp_change
elif len(word)<self.length:
return False
return False