LeetCode 79题中搜索字符串"bbbaabbbbbab"为何返回true但预期结果为false？

咱们拆解下你的代码为什么会返回错误的true，核心有几个逻辑漏洞，一个个来看：

1. 违反题目要求的搜索方向 #

题目明确说明只能走水平或垂直相邻的单元格（也就是上下左右四个方向），但你的DFS代码里多了一个对角线方向的递归调用：

dfs(board,i + 1, j + 1, wordIndex + 1, word,path)

这个方向完全不符合题目规则，这是导致错误匹配的关键原因之一——测试用例里的单词可能通过对角线走法被错误地匹配到，但实际上按照题目要求的合法路径是不存在的。

2. 冗余且逻辑错误的路径记录Stack #

你同时用了两种标记已访问单元格的方式：修改原网格字符为*，又用Stack记录坐标，但这两种方式不仅冗余，还导致了回溯逻辑混乱：

• Stack完全多余：既然已经通过board[i][j]='*'标记当前单元格已访问，回溯时再恢复为原字符，这种方式已经足够记录当前路径的访问状态，Stack的存在没有任何必要，反而添乱。
• Stack的回溯逻辑错误：只有在越界或字符不匹配时才执行path.pop()，但当DFS递归正常结束（比如四个方向都搜索完毕）时，没有将当前坐标从Stack中移除。这会导致Stack里的坐标越来越多，后续的DFS会错误地认为这些坐标已经被访问过，或者在某些情况下允许重复访问，彻底打乱了路径的正确性。

3. 初始判空的潜在Bug #

代码开头的if (word.equals(null))是错误的：如果word是null，调用equals(null)会直接抛出NullPointerException。正确的写法应该是if (word == null)，或者用Objects.isNull(word)（需要导入java.util.Objects）。

4. DFS的入口逻辑错误 #

进入DFS时的这段代码：

if (!path.contains("(" + String.valueOf(i) + "," + String.valueOf(j) + ")")) {
    path.push("(" + String.valueOf(i) + "," + String.valueOf(j) + ")");
}

完全没必要，而且和你用board[i][j]='*'的标记方式冲突。比如当回溯恢复了board[i][j]的字符，但Stack里还保留着这个坐标，后续其他路径走到这里时，会被Stack错误地拦截，导致合法路径被排除；反之，如果Stack没有正确移除坐标，也可能导致重复访问的错误。

修复建议 #

• 删掉对角线方向的递归调用，只保留上下左右四个方向；
• 完全移除Stack<String> path相关的所有代码，依赖修改原网格的方式来标记已访问即可；
• 修正word的判空逻辑；
• 调整DFS的回溯逻辑，确保只有当当前单元格被成功标记为已访问时，才在回溯时恢复它。

比如修正后的DFS大致如下：

private boolean dfs(char [][] board,int i, int j, int wordIndex, String word) {
    // 越界、字符不匹配直接返回false
    if (i < 0 || j < 0 || i >= board.length || j >= board[i].length || board[i][j] != word.charAt(wordIndex)) {
        return false;
    }
    // 匹配到最后一个字符，返回true
    if (wordIndex == word.length() - 1) {
        return true;
    }
    // 标记当前单元格为已访问
    char oldLetter = board[i][j];
    board[i][j]='*';
    // 搜索四个方向
    boolean found = dfs(board,i, j-1, wordIndex+1, word) ||
                    dfs(board,i, j+1, wordIndex+1, word) ||
                    dfs(board,i-1, j, wordIndex+1, word) ||
                    dfs(board,i+1, j, wordIndex+1, word);
    // 回溯，恢复原字符
    board[i][j] = oldLetter;
    return found;
}

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