如何在Boggle游戏板中递归搜索单词

Question

有人能帮我写一个伪代码，甚至是描述在Boggle板中递归搜索单词的递归公式吗？这样我就可以开始了？

Answer 1

假设您在某个地方有一个单词列表，很可能存储在Trie数据结构中（我在这里创建了一个工作的Trie，并对提高其效率发表了评论）。

一旦你有了一个Trie结构（前缀树），可以根据单词的前缀搜索单词，你就会想使用递归方法，比如下面的psudo代码。

char[][] gameBoard = new char[4][4];
List<String> wordList = new ArrayList<String>();
//fill in the game board with characters
//Start the word search at each letter
for(int x = 0; x < 4; x++){
    for(int y = 0; y < 4; y++){
        recursiveWordSearch(x, y, "");
    }
}
recursiveWordSearch(int x, int y, String word){
    //Concatenate gameBoard[x][y] to word.
    //Check to see if word is a valid word (check against your word list).
    //If word, add to wordList
    /*Check word list to see if any words contain current prefix. If not,
     then there's no point in continuing further (return). IE if AQZ isn't the 
     start of any word at all in the list, no reason to keep adding letters, it's
     never going to make a word.  */
    //Otherwise recursively call this method moving left/right/up/down
    recursiveWordSearch(x+1, y, word); //move right
    recursiveWordSearch(x, y+1, word); //move up
    recursiveWordSearch(x-1, y, word); //move left
    recursiveWordSearch(x, y-1, word); //move down
    /*You'll want to make sure that x-1, x+1, y-1 and y+1 are valid values before
     sending them. */

}

Answer 2

要存储有效单词，带有检查方法的数据结构会被给定某个有效单词的字符串前缀，并且被给定字符串需要一个有效单词，例如Trie数据结构。

为了找到所有可能的有效单词，我们必须为每个位置开始单词，然后递归地访问每个未访问的邻居。以下是python类的两种方法，它们实现了对给定表上所有有效单词的搜索：

def solve_with( self, ind, inds_passed, word):
    word += self.table[ind[0]][ind[1]]  # Add next character
    if self.trie.is_prefix(word):       # Is current string prefix of valid word
        if len(word) > 2 and self.trie.is_word(word):  # Is current string whole word
            self.ret.add(word)
        inds_passed.add(ind)            # Set this position as visited
        for n in self.neigbours(ind):   # Pass through all neighbours
            if n not in inds_passed:    # If not visited already
                self.solve_with(n, inds_passed, word)  # Recursive call
        inds_passed.discard(ind)        # Remove position as visited
def solve(self):
    self.ret = set()                    # Set of all word found on table
    for x in xrange(0, self.dim):       # Start search with each position
        for y in xrange(0, self.dim):
            self.solve_with( (x,y), set(), '')
    return self.ret

Answer 3

使用DFS方法的Java实现

import java.util.Arrays;
public class WordBoggle {
static int[] dirx = { -1, 0, 0, 1 };
static int[] diry = { 0, -1, 1, 0 };
public static void main(String[] args) {
    char[][] board = { { 'A', 'B', 'C', 'E' }, { 'S', 'F', 'C', 'S' }, { 'A', 'D', 'E', 'E' } };
    String word = "ABFSADEESCCEA";
    System.out.println(exist(board, word));
}
static boolean exist(char[][] board, String word) {
    if (board == null || board.length == 0 || word == null || word.isEmpty())
        return false;
    boolean[][] visited = new boolean[board.length][board[0].length];
    for (int i = 0; i < board.length; i++) {
        resetVisited(visited);
        for (int j = 0; j < board[0].length; j++) {
            if (board[i][j] == word.charAt(i)) {
                return DFS(board, word, i, j, 1, visited);
            }
        }
    }
    return false;
}
static void resetVisited(boolean[][] visited) {
    for (int l = 0; l < visited.length; l++) {
        Arrays.fill(visited[l], false);
    }
}
static boolean DFS(char[][] board, String word, int i, int j, int k, boolean[][] visited) {
    visited[i][j] = true;
    if (k >= word.length())
        return true;
    for (int z = 0; z < 4; z++) {
        if (isValid(board, i + dirx[z], j + diry[z], visited)) {
            if (word.charAt(k) == board[i + dirx[z]][j + diry[z]]) {
                return DFS(board, word, i + dirx[z], j + diry[z], k + 1, visited);
            }
        }
    }
    return false;
}