6 lines simple Python DFS

  • 1

    In my dfs step, curr means the current left partial word, x,y are the current indices in board, neighs means the available neighbors for next character. If there is no neighs and we haven't reached the last character, return False.

    class Solution(object):
        def exist(self, board, word):
            :type board: List[List[str]]
            :type word: str
            :rtype: bool
            m, n = len(board), len(board[0]) if board else 0
            def dfs(curr, (x,y), visited):
                if not curr: return True
                neighs = [(i,j) for i,j in ((x+1,y),(x-1,y),(x,y+1),(x,y-1)) if -1<i<m \
                          and -1<j<n and board[i][j] == curr[0] and (i,j) not in visited]
                return any(dfs(curr[1:], (i,j), visited|set([(i,j)])) for i,j in neighs)\
                       if neighs else False
            return not word or any(dfs(word[1:], (i,j), set([(i,j)])) for i in range(m) \
                   for j in range(n) if word[0] == board[i][j])

Log in to reply

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