AlgoViz Lab交互式算法学习Algorithms first
单词搜索 · 交互式算法学习
判断单词能否由相邻格且不重复使用格子组成。
#79 · 回溯
单词搜索
Word Search
board = [[A,B,C,E],[S,F,C,S],[A,D,E,E]], word = ABCCED矩阵3 个关键状态
步骤 1A 暂时标记为 #。
visitedA0,0
B0,1
C0,2
E0,3
S1,0
F1,1
C1,2
S1,3
A2,0
D2,1
E2,2
E2,3
推荐
原地标记回溯
时间
O(mn·4^L)空间 O(L)暂时把当前格改成标记，递归返回后恢复，省去集合复制。
1function exist(b, w) {2 function dfs(r, c, i) {3 if (i === w.length) return true;4 if (b[r]?.[c] !== w[i]) return false;5 const x = b[r][c];6 b[r][c] = '#';7 const ok = dfs(r + 1, c, i + 1) || dfs(r - 1, c, i + 1) || dfs(r, c + 1, i + 1) || dfs(r, c - 1, i + 1);8 b[r][c] = x;9 return ok10 }11 for (let r = 0; r < b.length; r++)12 for (let c = 0; c < b[0].length; c++)13 if (dfs(r, c, 0)) return true;14 return false;15}多语言参考
来源 · CC BY-SA 4.0 ↗Java · C++ · Go
这是一组同题正确实现，独立于上方当前动画方法；不同语言可能采用另一种正确策略。
1class Solution {2 private int m;3 private int n;4 private String word;5 private char[][] board;6 7 public boolean exist(char[][] board, String word) {8 m = board.length;9 n = board[0].length;10 this.word = word;11 this.board = board;12 for (int i = 0; i < m; ++i) {13 for (int j = 0; j < n; ++j) {14 if (dfs(i, j, 0)) {15 return true;16 }17 }18 }19 return false;20 }21 22 private boolean dfs(int i, int j, int k) {23 if (k == word.length() - 1) {24 return board[i][j] == word.charAt(k);25 }26 if (board[i][j] != word.charAt(k)) {27 return false;28 }29 char c = board[i][j];30 board[i][j] = '0';31 int[] dirs = {-1, 0, 1, 0, -1};32 for (int u = 0; u < 4; ++u) {33 int x = i + dirs[u], y = j + dirs[u + 1];34 if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] != '0' && dfs(x, y, k + 1)) {35 return true;36 }37 }38 board[i][j] = c;39 return false;40 }41}交互式算法学习
从执行步骤真正理解 LeetCode 经典 150
本站整理 150 道高频算法面试题和 302 种解法。动画方法同步展示 JavaScript 与 Python；每题另提供 Java、C++ 与 Go 同题参考实现。
AlgoViz Lab
单词搜索 · 解法对比
判断单词能否由相邻格且不重复使用格子组成。
- 测试用例
board = [[A,B,C,E],[S,F,C,S],[A,D,E,E]], word = ABCCED- 题目分类
- 回溯
- 解法对比
- 2
每个起点复制访问集合
从每格出发，路径携带已访问坐标集合。
- 时间
O(mn·4^L)- 空间
O(L)
原地标记回溯
暂时把当前格改成标记，递归返回后恢复，省去集合复制。
- 时间
O(mn·4^L)- 空间
O(L)