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


  • 0
    L

    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]:
            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

    ["ABCE",

    "SFES",

    "ADEE"]

    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?


  • 0
    B

    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


  • 2
    S

    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.


Log in to reply
 

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