Python 3 DFS Solution


#1
def dfs(A,word,pos,curr_pos):
    if pos>=len(word):
        return True
    if A[curr_pos[0]][curr_pos[1]] != word[pos]:
        return False
    for pos_i,pos_j in [(0,-1),(-1,0),(0,1),(1,0)]:  
        next_i,next_j = (curr_pos[0]+pos_i,curr_pos[1]+pos_j)
        if next_i>=0 and next_i<len(A) and next_j>=0 and next_j<len(A[0]):
            if dfs(A,word,pos+1,(next_i,next_j)):
                return True

class Solution:
    def exist(self, A, B):
        for i in range(len(A)):
            for j in range(len(A[0])):
                    if A[i][j]==B[0] and dfs(A,B,0,(i,j)):
                        return 1
        return 0