我正在处理一个单词搜索问题。我正确实现了 dfs 搜索，但在其他地方出现了琐碎的错误。
对于此列表中的单词 ["oath","pea","eat","rain"]，可以在板上找到“oath”和“eat”：
[
['o','a','a','n'],
['e','t','a','e'],
['i','h','k','r'],
['i','f','l','v']
]
我设计了一个程序来搜索给定板上的所有单词。这是我使用 dfs 的代码：
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;
}
}
对于上面给出的示例，我的代码奇怪地返回了 [eat, eat]。
因为我遍历单词列表并判断它们是否可以在板上找到。即使我没有找到“誓言”，“吃”也不应该在结果列表中添加两次。