Python DFS solution


  • 8
    G
    class Solution:
        # @param board, a list of lists of 1 length string
        # @param word, a string
        # @return a boolean
        # 3:42
        def exist(self, board, word):
            visited = {}
    
            for i in range(len(board)):
                for j in range(len(board[0])):
                    if self.getWords(board, word, i, j, visited):
                        return True
            
            return False
    
        def getWords(self, board, word, i, j, visited, pos = 0):
            if pos == len(word):
                return True
    
            if i < 0 or i == len(board) or j < 0 or j == len(board[0]) or visited.get((i, j)) or word[pos] != board[i][j]:
                return False
    
            visited[(i, j)] = True
            res = self.getWords(board, word, i, j + 1, visited, pos + 1) \
                    or self.getWords(board, word, i, j - 1, visited, pos + 1) \
                    or self.getWords(board, word, i + 1, j, visited, pos + 1) \
                    or self.getWords(board, word, i - 1, j, visited, pos + 1)
            visited[(i, j)] = False
    
            return res

  • 1
    S

    Great Code! I previously use code like

    dfs()
     visited[i-1,j] = true;
     dfs(i-1,j)
     visited[i-1,j] = false;
    
     visited[i+1,j] = true;
     dfs(i+1,j)
     visited[i+1,j] = false;
    
     visited[i,j-1] = true;
     dfs(i,j-1)
     visited[i,j-1] = false;
     
     visited[i,j+1] = true;
     dfs(i,j+1)
     visited[i,j+1] = false;
    

    and get TLE for {"aaaa...","aaaa...."} case. Still dont' understand what's the difference

    Modified java code based on your idea.

    public class Solution {
        public boolean exist(char[][] board, String word) {
            // edge case
            if(word == null || board == null || board.length == 0) return false;
            
            boolean[][] used = new boolean[board.length][board[0].length];
            for(int i = 0;i < board.length;i++)
                for(int j = 0;j < board[0].length;j++)
                    if(dfs(board, i, j, word, 0, used)) return true;
            return false;
        }
        
        private boolean dfs(char[][] board, int x, int y, String word, int index, boolean[][] used){
            // ending case
            if(index==word.length()) return true;
            
            if(x < 0 || x >= board.length || y < 0 || y >= board[0].length) return false;
            
            if(used[x][y] || board[x][y]!=word.charAt(index)) return false;
            
            // recursive call
            used[x][y] = true;
            if(dfs(board,x-1,y,word,index+1,used)) return true;
            if(dfs(board,x+1,y,word,index+1,used)) return true;
            if(dfs(board,x,y-1,word,index+1,used)) return true;
            if(dfs(board,x,y+1,word,index+1,used)) return true;
            used[x][y] = false;
            
            return false;
        }
    }
    

  • 0
    H

    It is curious that or instead of "|" can be accepted, something to do with parallelism?


  • 0
    S

    Where is it?


  • 0
    H

    here is the code

    class Solution:
    def f(self,board,word,i,j,visited,pos=0):
    if len(word)==pos:
    return True
    if i<0 or i>=len(board) or j<0 or j>=len(board[0]) or visited.get((i,j)) or word[pos]!=board[i][j]:
    return False

        visited[(i,j)]=True
       
        res=self.f(board,word,i,j+1,visited,pos+1)\
        |self.f(board,word,i ,j-1,visited,pos+1)\
        |self.f(board,word,i+1,j ,visited,pos+1)\
        |self.f(board,word,i-1,j,visited,pos+1)
        visited[(i,j)]=False
        return res
    # @param board, a list of lists of 1 length string
    # @param word, a string
    # @return a boolean
    def exist(self, board, word):
    
             
        visited={}
    
        for i in range(len(board)):
            for j in range(len(board[0])):
                #print i,j
                if self.f(board,word,i,j,visited):
                    return True
                 
        return False
    

    change '|' to 'or' will TLE


  • 1
    J

    "|" is a binary operator, whereas "or" is a logical operator, which means "or" will stop once True is met, "|" won't. That's the difference.


  • 0
    H

    I see now, just like the difference between | and || in C++, thank you very much!


  • 1
    C

    Nice idea, here is a revised version of your code:

    def exist(self, board, word):
        if not board:
            return False
        r, c = len(board), len(board[0])
        visited = [[False for i in xrange(c)] for j in xrange(r)]
        for i in xrange(r):
            for j in xrange(c):
                if self.dfs(board, word, visited, i, j):
                    return True
        return False
        
    def dfs(self, board, word, visited, i, j):
        if not word:
            return True
        if i < 0 or i == len(board) or j < 0 or j == len(board[0]) \
        or visited[i][j] or word[0] != board[i][j]:
            return False
        visited[i][j] = True
        res = self.dfs(board, word[1:], visited, i+1, j) or \
              self.dfs(board, word[1:], visited, i-1, j) or \
              self.dfs(board, word[1:], visited, i, j-1) or \
              self.dfs(board, word[1:], visited, i, j+1)
        visited[i][j] = False
        return res

  • 0
    Z

    Could you explain what does visited[(i,j)]=False mean?


Log in to reply
 

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