3
我工作的一個詞搜索問題。我正確實施了dfs搜索，但其他地方存在trival錯誤。單詞搜索使用深度優先搜索
對於此列表中字[「誓言」，「豌豆」，「吃」，「雨」]，「誓言」和「吃」可以在主板上找到：
[
['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]。
由於我遍歷單詞列表並判斷它們是否可以在董事會中找到。儘管我沒有找到'誓言'，但'吃'不應該在結果列表中添加兩次。