Here's my Python code using DFS.
class Solution: # @param board, a list of lists of 1 length string # @param word, a string # @return a boolean def exist(self, board, word): res = False for i in xrange(len(board)): for j in xrange(len(board[i])): if board[i][j] == word: res |= self.dfs(board, i, j, word, set()) if res: break return res def dfs(self, board, i, j, word, walked): if len(word) == 0 or (len(word) == 1 and board[i][j] == word): return True res = False if board[i][j] == word: walked.add((i,j)) if i > 0 and (i-1,j) not in walked: res |= self.dfs(board, i-1, j, word[1:], walked) if i < len(board)-1 and (i+1,j) not in walked: res |= self.dfs(board, i+1, j, word[1:], walked) if j > 0 and (i,j-1) not in walked: res |= self.dfs(board, i, j-1, word[1:], walked) if j < len(board[i])-1 and (i,j+1) not in walked: res |= self.dfs(board, i, j+1, word[1:], walked) return res
Somehow I got the wrong answer with the input
and the target "ABCESEEEFS"
I think the answer is False because you can't find the word "ABCESEEEFS" sequentially in the board. However the expected answer is True. Am I misunderstood this problem?
The expected answer should be True, here is the pattern
A B C E
S F E S
Basically you go from left to right first and get ABCE; then go all the way to bottom and get ABCESE; then go left to the 2nd col and get ABCESEE; then go up to the 2nd row and get ABCESEEE; finally go left to get ABCESEEEFS
I don't know much about Python. I had my Java Solution Accepted. The problem you encountered is because you didn't set the wrong path nodes back to "unwalked". The way I do it in Java is define a "current_path" which notes down the current path (probably use a stack) and also a subtree array to note down how many sub path a node has. Once you encounter a wrong end node, which the subtree value is 0, you trace back the current path, set these nodes to "unwalked" until the node has more than 1 subtree. And then continue dfs on that node's another subtree.