难度**

**中等

思路

DFS + 剪枝

  • DFS，Deep First Search，深度优先搜索算法。类似树的前序遍历（从左走，走到尽头才回头）。
  • 剪枝
    • 在搜索中，遇到 不可能 情况则应立即返回，称为 可行性剪枝。 ```java

/**

  • DFS + 剪枝 *
  • @param board
  • @param word

  • @return */ public static boolean exist_1(char[][] board, String word) { char[] wordChars = word.toCharArray();

    // 二数组每个位置都可做起始点 for (int i = 0; i < board.length; i++) {

    1.  for (int j = 0; j < board[0].length; j++) {
    2.      // 从该点做DFS搜索，如果字符串存在，则返回 true，否则继续下一个节点
    3.      if (doRecursion(i, j, 0, board, wordChars)) {
    4.          return true;
    5.      }
    6.  }

    } return false; }

public static boolean doRecursion(int i, int j, int k, char[][] board, char[] word) { // 边界条件判断 if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || word[k] != board[i][j]) { return false; }

// 成功找到最后一个元素
if (k == word.length - 1) {
    return true;
}

// 对已遍历的数据做标记
char temp = board[i][j];
board[i][j] = '\0';

// 从四个方向查找
// 重点: 不能用k++替代k+1，因为，这会改变后续的指针情况
boolean ret = doRecursion(i, j - 1, k+1, board, word)           // 向左
        || doRecursion(i, j + 1, k+1, board, word)              // 向右
        || doRecursion(i - 1, j, k+1, board, word)              // 向上
        || doRecursion(i + 1, j, k+1, board, word);             // 向下


// 重点: 还原数据
// 回溯后还原数据
board[i][j] = temp;
return ret;

} ``` | 时间复杂度 | O(3**MN)** | | —- | —- | | 空间复杂度 | O(k) |

  • M: 表示矩阵行大小
  • N: 表示矩阵列大小

  • k: 表示递归深度

    总结

  • 这题难度还是比较高的，一开始是设想通过存储已走过的节点到栈中，然后再继续向下搜索，当回溯时，判断栈顶元素是否与当前元素相等，如果相等，则表示此条路已经走过，但是这存储无疑是一个具大的开销。于是，我们可以转变思路，使用栈来保存已遍历过的状态，并在递归完之后恢复原值。这样，就不需要额外的存储空间存储已走过的节点的位置。

  • 这一题能让我加深对 递归 的理解，递归可以用来保存旧有状态，还可以修改部分值，并在递归完之后恢复现场。使用递归需要清晰知道 递归 结束条件以及 构建递归表达式。