3

私は単語検索の問題に取り組んでいます。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] を返しました。

単語のリストを反復処理し、ボードで見つかるかどうかを 1 つずつ判断します。'oath' が見つからなかったとしても、'eat' が結果リストに 2 回追加されることはありません。

4

1 に答える 1

2

これが問題のようです：

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;
于 2015-11-02T06:43:15.777 に答える