使用深度优先搜索的单词搜索

Question

我在处理一个单词搜索问题。我正确地实现了dfs搜索，但在其他地方有一些琐碎的错误。

[ 
 ['o','a','a','n'],
 ['e','t','a','e'],
 ['i','h','k','r'],
 ['i','f','l','v']
                  ]

public class WordSearchII {
public List<String> findWords(char[][] board, String[] words) {

    List<String> res = new ArrayList<String>();

    // in order to reinitailize the board every time after 
    //I search each word in the board
    char[][] temp = new char[board.length][board[0].length];
    for (int i=0; i<board.length; i++){
            for(int j=0; j<board[i].length; j++){
                temp[i][j]=board[i][j];
            }
        }

    for (String word : words){
        board=temp; //reintialize the board
        for (int i=0; i<board.length; i++){
            for(int j=0; j<board[i].length; j++){
                if (find_word(board, word, i, j, 0))// bfs search
                res.add(word);
            }
        }
    }
    return res;
}

public boolean find_word(char[][] board, String word, int i, int j, int index){

    if (index==word.length()) return true;

    if (i<0 || i>=board.length || j<0 || j>=board[i].length) return false;

    if (board[i][j]!=word.charAt(index)) return false;

    char temp=board[i][j];

    board[i][j] = '*';

    if (find_word(board, word, i-1, j, index++)||
        find_word(board, word, i+1, j, index++)||
        find_word(board, word, i, j-1, index++)||
        find_word(board, word, i, j+1, index++)) return true;

    board[i][j]= temp;

    return false;

}
}

Answer 1

这似乎就是问题所在：

if (find_word(board, word, i-1, j, index++)||
    find_word(board, word, i+1, j, index++)||
    find_word(board, word, i, j-1, index++)||
    find_word(board, word, i, j+1, index++)) return true;

每次都要递增索引，但必须将index+1传递给每个子调用。

if (find_word(board, word, i-1, j, index+1)||
    find_word(board, word, i+1, j, index+1)||
    find_word(board, word, i, j-1, index+1)||
    find_word(board, word, i, j+1, index+1)) return true;