# Wrong Answer: Input: ["ABCE","SFES","ADEE"], "ABCESEEEFS" Output: false Expected: true

• 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[0]:
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[0]):
return True
res = False
if board[i][j] == word[0]:
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

["ABCE",

"SFES",

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
E E
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.

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