79. Word Search

Link

Solution

根據每個board裡面元素進行DFS 看看結果為何

public boolean exist(char[][] board, String word) {
        if(word.equals("") && word == null) return true;
        if(board.length == 0) return false;
        char[] wordChar = word.toCharArray();
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[0].length; j++){
                if(dfs(board, wordChar, 0, i , j)){
                    return true;
                }
                
            }
        }
        return false;
    }
    
    public boolean dfs(char[][] board, char[] wordChar, int index, int i, int j){
        
        if(index >= wordChar.length) return true;
        
        if(i >= board.length || i < 0 || j < 0 || j >= board[0].length) return false; 
        
        boolean ret = false;
        if(wordChar[index] == board[i][j]){
            
            board[i][j] = ' '; //visited
            
            ret = dfs(board, wordChar, index+1, i+1, j) ||
            dfs(board, wordChar, index+1, i, j+1) ||
            dfs(board, wordChar, index+1, i-1, j) ||
            dfs(board, wordChar, index+1, i, j-1);
            
            board[i][j] = wordChar[index]; //restored to unvisited
        }
        return ret;
    }