Share my Java code [straightforward DFS]


  • 3
    M
    public class Solution {
        public boolean exist(char[][] board, String word) {
            if (word == null || word.length() == 0) {
                return false;
            }
            boolean[][] isBeingVisited = 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 (board[i][j] == word.charAt(0) &&
                        dfs(board, word, isBeingVisited, 0, i, j)) {
                        return true;
                    }
                }
            }
            return false;
        }
        
        private boolean dfs(char[][] board, String word, boolean[][] isBeingVisited, int index, int row, int col) {
            if (index == word.length()) {  // reached the end of the word
                return true;
            }
            if (row < 0 || row >= board.length || col < 0 || col >= board[0].length
                || isBeingVisited[row][col] || word.charAt(index) != board[row][col]) {
                return false;    
            }
            isBeingVisited[row][col] = true;
            if (dfs(board, word, isBeingVisited, index + 1, row - 1, col)) {
                return true;
            }
            if (dfs(board, word, isBeingVisited, index + 1, row + 1, col)) {
                return true;
            }
            if (dfs(board, word, isBeingVisited, index + 1, row, col - 1)) {
                return true;
            }
            if (dfs(board, word, isBeingVisited, index + 1, row, col + 1)) {
                return true;
            }
            isBeingVisited[row][col] = false;  // umark current point; it might be used in other routes
            return false;
        }
    }

  • 0
    I

    Did this give you time limit exceeded?


  • 0
    M

    @IWantToPass No, it can still be accepted currently.


  • 0
    I

    Hmm, I implemented the same in python and it is not passing :(


  • 0
    M

    below is the naive straightforward translation to python, still can be accepted...


  • 0
    M
    1. There is no need to rebuild/reinitialize the "visited" array each (i, j). Since if the word is not found, the "visited" array would be restored to its initial state (all false) during backtracking.
    1. Instead of terminating the dfs at "index == len(word)", you can do it at "index == len(word) - 1", thus you would spare 1 level of recursion, which would be time-saving. The former one beats 65.01% run times, while the latter one beats 92.33%.
    class Solution(object):
        def exist(self, board, word):
            """
            :type board: List[List[str]]
            :type word: str
            :rtype: bool
            """
            def dfs(board, visited, row, col, word, index):
                if (index == len(word)): return True
                if (row < 0 or row >= len(board) or col < 0 or col >= len(board[0]) or visited[row][col] or word[index] != board[row][col]): return False
                visited[row][col] = True
                if dfs(board, visited, row + 1, col, word, index + 1): return True
                if dfs(board, visited, row - 1, col, word, index + 1): return True
                if dfs(board, visited, row, col + 1, word, index + 1): return True
                if dfs(board, visited, row, col - 1, word, index + 1): return True
                visited[row][col] = False
                return False
            
            visited = [[False for _ in xrange(0, len(board[0]))] for _ in xrange(0, len(board))]
            for i in xrange(0, len(board)):
                for j in xrange(0, len(board[0])):
                    if board[i][j] == word[0] and dfs(board, visited, i, j, word, 0): return True
            return False
    

    class Solution(object):
        def exist(self, board, word):
            """
            :type board: List[List[str]]
            :type word: str
            :rtype: bool
            """
            def dfs(board, visited, row, col, word, index):
                if (index == len(word) - 1): return word[-1] == board[row][col]
                if (word[index] != board[row][col]): return False
                visited[row][col] = True
                if row + 1 < len(board) and not visited[row + 1][col] and dfs(board, visited, row + 1, col, word, index + 1):
                    return True
                if row - 1 >= 0 and not visited[row - 1][col] and dfs(board, visited, row - 1, col, word, index + 1):
                    return True
                if col + 1 < len(board[0]) and not visited[row][col + 1] and dfs(board, visited, row, col + 1, word, index + 1): return True
                if col - 1 >= 0 and not visited[row][col - 1] and  dfs(board, visited, row, col - 1, word, index + 1):
                    return True
                visited[row][col] = False
                return False
            
            visited = [[False for _ in xrange(0, len(board[0]))] for _ in xrange(0, len(board))]
            for i in xrange(0, len(board)):
                for j in xrange(0, len(board[0])):
                    if board[i][j] == word[0] and dfs(board, visited, i, j, word, 0): return True
            return False
    

  • 0
    M

    Also, if your logic is correct, there are 2 tips for boosting the running time. See my answer below.


  • 0
    I

    I tried your suggestions, it still does not pass the OJ it gives a wrong answer. Here is my code:

    class Solution(object):
        def exist(self, board, word):
            """
            :type board: List[List[str]]
            :type word: str
            :rtype: bool
            """
            if not word:
                return False
            
            rows, cols = len(board), len(board[0])
            visited = [[False]*cols]*rows
            
            for row in xrange(rows):
                for col in xrange(cols):
                    if board[row][col] == word[0] and self.backTrack(board, word, 0, row, col, visited):
                        return True
            return False
            
        def backTrack(self, board, word, wordIdx, row, col, visited):                
            if row < 0 or row >= len(board) or col < 0 or col >= len(board[0]) or (visited[row][col]) or (word[wordIdx] != board[row][col]):
                return False
    
            if wordIdx == len(word) - 1:
                return True
                
            visited[row][col] = True
            
            if self.backTrack(board, word, wordIdx + 1, row + 1, col, visited):
                return True
                
            if self.backTrack(board, word, wordIdx + 1, row - 1, col, visited):
                return True
                
            if self.backTrack(board, word, wordIdx + 1, row, col + 1, visited):
                return True
                
            if self.backTrack(board, word, wordIdx + 1, row, col - 1, visited):
                return True
                
            visited[row][col] = False
            return False

  • 0
    M

    your code is right, except for the initialization of 2d visited array visited = [[False]*cols]*rows. it will create only 1 unique row, the rest rows are all its shallow copy. you should use list comprehension visited = [[False for i in range(0, cols)] for j in range(0, rows)] to initialize the 2d array. http://www.kosbie.net/cmu/fall-11/15-112/handouts/notes-2d-lists.html. if you find it helpful, please upvote me :p


  • 0
    I

    Ah ok thanks, I did not know that. Thank you.


Log in to reply
 

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