递归地在网格中查找单词

Question

我正在做一道算法题，以便在网格上找到一个词。

我的解决方案包括首先在网格中找到单词的第一个字母，如果找到，则递归遍历 8 个方向，直到单词的每个索引都与网格索引匹配，并且 return字符串。附上我的代码：

我跟踪我当前的 x 和 y 位置，然后当且仅当单词的索引与网格中的索引匹配时才增加字符串的位置。但是，对于这段代码，我的递归有问题导致堆栈溢出：

public static void findWord(int row, int col, char[][] grid, String w) {
    int rowLength = row;
    int colLength = col;

    char[] word = w.toCharArray();

    for(int j = 0; j < colLength; j++) {
        for(int i = 0; i < rowLength; i++) {
            // Check if first index of word is in this location
            if(word[0] == grid[j][i]) {
                // Iterate through each 8 directions to find the next word
                for(int dir = 0; dir < 8; dir++) {
                    recursiveFind(i, j, i, j, dir, 0, word, grid, rowLength, colLength);
                }
            }
        }
    }
}

public static boolean recursiveFind(
        int initialX, 
        int initialY, 
        int currentX, 
        int currentY, 
        int dir, 
        int currentPos, 
        char[] word, 
        char[][] grid, 
        int rowLength, 
        int colLength) 
{
    // base case is if currentPos == length of word
    if(word.length == currentPos) {
        System.out.println("Initial: " + initialX + " " + initialY);
        System.out.println("Final: " + currentX + " " + currentY);
    }

    if(dir == 0) { // 1
        currentX = currentX; // 0
        currentY -= 1; // -1
    } else if(dir == 1) {
        currentX += 1; // 1
        currentY -= 1; // -1
    } else if(dir == 2) {
        currentX += 1; // 1
        currentY = 0; // 0
    } else if(dir == 3) {
        currentX += 1; // 1
        currentY += 1; // 1
    } else if(dir == 4) {
        currentX = currentX; // 0
        currentY += 1;  // 1
    } else if(dir == 5) {
        currentX -= 1; // -1
        currentY += 1; // 1
    } else if(dir == 6) {
        currentX -= 1; // -1
        currentY = currentY; // 0
    } else {
        currentX -= 1; // -1
        currentY -= 1; // -1
    }

    if(currentX < 0 || 
            currentX == rowLength || 
            currentY < 0 || 
            currentY == colLength || 
            grid[currentY][currentX] != word[currentPos]){
        return false;
    }
    return recursiveFind(initialX, initialY, currentX, currentY, dir, currentPos + 1, word, grid, rowLength, colLength);
}

Main.java

    char[][] myGrid = new char[][]{
            {'H', 'Q', 'W', 'C', 'S'}, 
            {'E', 'S', 'P', 'K', 'D'}, 
            {'D', 'X', 'A', 'F', 'L'}, 
            {'O', 'C', 'H', 'K', 'H'}, 
            {'C', 'T', 'Y', 'C', 'A'}, 
    };

    String myWord = "CODE";

    findWord(5, 5, myGrid, myWord);

我目前正在尝试添加一些调试语句以查看问题所在，但是，如果有人愿意为此提供一些帮助，我们将不胜感激！

编辑：

我在基本案例中通过 return true 修复了 Stack Overflow 问题。但是，我的结果如下，return 不是我想要的预期值。

Initial X: 3, Initial Y: 0, Dir: 0, Current X: 3, Current Y: 0
Initial X: 3, Initial Y: 0, Dir: 1, Current X: 3, Current Y: 0
Initial X: 3, Initial Y: 0, Dir: 2, Current X: 3, Current Y: 0
Initial X: 3, Initial Y: 0, Dir: 3, Current X: 3, Current Y: 0
Initial X: 3, Initial Y: 0, Dir: 4, Current X: 3, Current Y: 0
Initial X: 3, Initial Y: 0, Dir: 5, Current X: 3, Current Y: 0
Initial X: 3, Initial Y: 0, Dir: 6, Current X: 3, Current Y: 0

Answer 1

乍一看，我认为问题可能是当currentpos达到字长时你没有终止递归，所以它会继续下去直到溢出。基本情况应该结束递归，但如果不满足 return false 的条件，你的递归会继续。

编辑：我很确定目录 2 的条件应该是：

else if(dir == 2) {
        currentX += 1; // 1
        currentY = currentY; // 0
    }

否则您将重新启动当前的 Y，就像您现在拥有的那样

编辑：此外，您不应在递归开始时将 currentpos 发送为 0，因为它会再次与单词的第一个字母进行比较。递归应该开始与第二个字符进行比较，因为您已经比较了第一个字符。不要忘记添加 return true，您的程序应该运行。我刚刚在我的电脑上试过了。

Answer 2

我改了一下，检查当前位置是否正确，然后继续搜索。否则，return false.

public static boolean recursiveFind(
        int initialX,
        int initialY,
        int currentX,
        int currentY,
        int dir,
        int currentPos,
        char[] word,
        char[][] grid,
        int rowLength,
        int colLength) {
    // base case is if currentPos == length of word
    if (word.length == currentPos) {
        System.out.println("Initial: " + initialX + " " + initialY);
        System.out.println("Final: " + currentX + " " + currentY);
        return true;
    }

    if (currentX >= 0 && currentX < rowLength && currentY >= 0 && currentY < colLength && grid[currentY][currentX] == word[currentPos]) {
        if (dir == 0) { // 1
            currentX = currentX; // 0
            currentY -= 1; // -1
        } else if (dir == 1) {
            currentX += 1; // 1
            currentY -= 1; // -1
        } else if (dir == 2) {
            currentX += 1; // 1
            currentY = 0; // 0
        } else if (dir == 3) {
            currentX += 1; // 1
            currentY += 1; // 1
        } else if (dir == 4) {
            currentX = currentX; // 0
            currentY += 1; // 1
        } else if (dir == 5) {
            currentX -= 1; // -1
            currentY += 1; // 1
        } else if (dir == 6) {
            currentX -= 1; // -1
            currentY = currentY; // 0
        } else {
            currentX -= 1; // -1
            currentY -= 1; // -1
        }

        return recursiveFind(initialX, initialY, currentX, currentY, dir, currentPos + 1, word, grid, rowLength, colLength);
    }

    return false;

}

编辑：在您最近的编辑中，问题是您在检查当前位置之前更改了 currentX/currentY。

这段代码：

if(currentX < 0 || 
        currentX == rowLength || 
        currentY < 0 || 
        currentY == colLength || 
        grid[currentY][currentX] != word[currentPos]){
    return false;
}

必须在您执行之前发生：

if(dir == 0) { // 1
    currentX = currentX; // 0
    currentY -= 1; // -1
} else if(dir == 1) {
    currentX += 1; // 1
    currentY -= 1; // -1
} else if(dir == 2) {
    currentX += 1; // 1
    currentY = 0; // 0
} else if(dir == 3) {
    currentX += 1; // 1
    currentY += 1; // 1
} else if(dir == 4) {
    currentX = currentX; // 0
    currentY += 1;  // 1
} else if(dir == 5) {
    currentX -= 1; // -1
    currentY += 1; // 1
} else if(dir == 6) {
    currentX -= 1; // -1
    currentY = currentY; // 0
} else {
    currentX -= 1; // -1
    currentY -= 1; // -1
}

否则你并没有真正检查当前位置:P

递归地在网格中查找单词

Recursively find a word in a grid

java

grid

recursion

word