85ms java dfs with cache fyi


  • 0
    S
    public class Solution {
    public boolean exist(char[][] board, String word) {
        
        Set<Long> visited = new HashSet<Long>(); 
        for(int row=0; row<board.length; row++) {
            for(int col=0; col<board[0].length; col++) { 
                if(board[row][col] == word.charAt(0)) { 
                    if(matchDfs(board, row, col, word, 0, visited)) { 
                        return true;     
                    }
                }
            }
        }
        return false;    
    }
    
    private boolean matchDfs(char[][] board, int row, int col, String word, int wordIdx, Set<Long> visited) { 
        if(row < 0 || row >= board.length) return false; 
        if(col < 0 || col >= board[0].length) return false; 
        if(visited.contains(getVisitedKey(row, col)) || board[row][col] != word.charAt(wordIdx)) return false; 
        
        if(wordIdx == word.length()-1) return true; 
        
        Long visitedKey = getVisitedKey(row, col);
        visited.add(visitedKey);
        boolean match = matchDfs(board, row-1, col, word, wordIdx+1, visited) || 
                        matchDfs(board, row+1, col, word, wordIdx+1, visited) || 
                        matchDfs(board, row, col-1, word, wordIdx+1, visited) || 
                        matchDfs(board, row, col+1, word, wordIdx+1, visited);
        
        if(!match) { 
            visited.remove(visitedKey);
        }
        
        return match;  
    }
    
    private Long getVisitedKey(int row, int col) {
        return (Long.valueOf(row) << 32) | Long.valueOf(col); 
    }
    

    }


Log in to reply
 

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