网格单词计数问题：如何实现最多一次转向的单词匹配？

给定字符网格与单词数组，需判断每个单词是否存在于网格中，移动规则如下：

• 可从任意单元格出发
• 仅允许左→右或上→下方向移动
• 最多可转向一次（如先左→右，再转为上→下）

示例 #

Grid #

[
  ["c", "o", "d", "g"],
  ["a", "t", "e", "r"],
  ["z", "o", "p", "s"]
]

words数组 #

["code", "coder", "cat", "top", "spot"]

结果 #

符合条件的单词数量为3

解释 #

• "code"有效：路径为[0][0]→[0][1]→[0][2]→[1][2]，中途转向一次
• "coder"无效：需转向两次
• "cat"有效：路径为[0][0]→[1][0]→[1][1]
• "top"有效：路径为[1][1]→[2][1]→[2][2]
• "spot"无效：方向为右→左与下→上（不符合允许的方向）

现有代码仅实现了行列单向的单词匹配，无法处理最多一次转向的场景，代码如下：

public static boolean wordExists(char[][] matrix, String word) {
    // Check each row
    for (char[] row : matrix) {
        if (checkRow(row, word)) {
            return true;
        }
    }

    // Check each column
    for (int col = 0; col < matrix[0].length; col++) {
        char[] column = new char[matrix.length];
        for (int row = 0; row < matrix.length; row++) {
            column[row] = matrix[row][col];
        }
        if (checkRow(column, word)) {
            return true;
        }
    }

    return false;
}

private static boolean checkRow(char[] row, String word) {
    int charIndex = 0;
    for (char c : row) {
        if (c == word.charAt(charIndex)) {
            charIndex++;
            if (charIndex == word.length()) {
                return true;
            }
        } else {
            charIndex = 0; // Start over if character mismatch
        }
    }
    return false;
}

需要实现支持最多一次转向的单词匹配逻辑，完成网格中符合条件的单词计数。

要支持最多一次转向的匹配，需覆盖三种核心场景：

1. 纯水平（左→右）方向匹配
2. 纯垂直（上→下）方向匹配
3. 先水平后垂直的转向匹配（左→右走一段，再转上→下）

核心思路 #

• 遍历网格中的每个单元格作为起点
• 对每个起点，分别尝试三种匹配场景，只要任意一种成功，该单词即符合条件

完整代码实现 #

public class WordMatcher {

    public static int countValidWords(char[][] matrix, String[] words) {
        int validCount = 0;
        for (String word : words) {
            if (isWordValid(matrix, word)) {
                validCount++;
            }
        }
        return validCount;
    }

    private static boolean isWordValid(char[][] matrix, String word) {
        int rows = matrix.length;
        if (rows == 0 || word.isEmpty()) return false;
        int cols = matrix[0].length;
        int wordLength = word.length();

        // 遍历所有可能的起点
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] != word.charAt(0)) continue;

                // 检查纯水平匹配
                if (checkHorizontal(matrix, i, j, word)) return true;
                // 检查纯垂直匹配
                if (checkVertical(matrix, i, j, word)) return true;
                // 检查先水平后垂直的转向匹配
                if (checkHorizontalThenVertical(matrix, i, j, word)) return true;
            }
        }
        return false;
    }

    // 检查从(i,j)开始水平向右匹配整个单词
    private static boolean checkHorizontal(char[][] matrix, int i, int j, String word) {
        int cols = matrix[0].length;
        int wordLen = word.length();
        if (j + wordLen > cols) return false;

        for (int k = 0; k < wordLen; k++) {
            if (matrix[i][j + k] != word.charAt(k)) return false;
        }
        return true;
    }

    // 检查从(i,j)开始垂直向下匹配整个单词
    private static boolean checkVertical(char[][] matrix, int i, int j, String word) {
        int rows = matrix.length;
        int wordLen = word.length();
        if (i + wordLen > rows) return false;

        for (int k = 0; k < wordLen; k++) {
            if (matrix[i + k][j] != word.charAt(k)) return false;
        }
        return true;
    }

    // 检查先水平向右走k步，再垂直向下走剩余步数（k从1到wordLen-1）
    private static boolean checkHorizontalThenVertical(char[][] matrix, int i, int j, String word) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        int wordLen = word.length();

        // 遍历所有可能的转向点：水平走1到wordLen-1个字符后转垂直
        for (int k = 1; k < wordLen; k++) {
            // 水平方向长度不足，跳过
            if (j + k > cols) continue;
            // 验证水平段是否匹配
            boolean horizontalOk = true;
            for (int m = 0; m < k; m++) {
                if (matrix[i][j + m] != word.charAt(m)) {
                    horizontalOk = false;
                    break;
                }
            }
            if (!horizontalOk) continue;

            // 垂直方向长度不足，跳过
            int verticalSteps = wordLen - k;
            if (i + verticalSteps > rows) continue;
            // 验证垂直段是否匹配
            boolean verticalOk = true;
            for (int m = 0; m < verticalSteps; m++) {
                if (matrix[i + m][j + k - 1] != word.charAt(k + m)) {
                    verticalOk = false;
                    break;
                }
            }
            if (verticalOk) return true;
        }
        return false;
    }

    // 测试用例
    public static void main(String[] args) {
        char[][] grid = {
            {'c', 'o', 'd', 'g'},
            {'a', 't', 'e', 'r'},
            {'z', 'o', 'p', 's'}
        };
        String[] words = {"code", "coder", "cat", "top", "spot"};
        System.out.println("符合条件的单词数量：" + countValidWords(grid, words)); // 输出3
    }
}

代码说明 #

1. countValidWords：遍历所有单词，统计符合条件的数量
2. isWordValid：对单个单词，遍历所有起点，依次检查三种匹配场景
3. checkHorizontal/checkVertical：处理纯水平/垂直的单向匹配逻辑
4. checkHorizontalThenVertical：遍历所有可能的转向点，分别验证水平段和垂直段的匹配情况

运行测试用例后，输出结果为3，与题目示例完全一致。

内容的提问来源于stack exchange，提问作者Learner