//Java class Solution { public boolean exist(char[][] board, String word) { int h = board.length, w = board[0].length; boolean[][] visited = new boolean[h][w]; for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { boolean flag = check(board, visited, i, j, word, 0); if (flag) { return true; } } } return false; }
public boolean check(char[][] board, boolean[][] visited, int i, int j, String s, int k) { if (board[i][j] != s.charAt(k)) { return false; } else if (k == s.length() - 1) { return true; } visited[i][j] = true; int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; boolean result = false; for (int[] dir : directions) { int newi = i + dir[0], newj = j + dir[1]; if (newi >= 0 && newi < board.length && newj >= 0 && newj < board[0].length) { if (!visited[newi][newj]) { boolean flag = check(board, visited, newi, newj, s, k + 1); if (flag) { result = true; break; } } } } visited[i][j] = false; return result; } }
这个问题可以看作有 n 个排列成一行的空格，我们需要从左往右依此填入题目给定的 n 个数，每个数只能使用一次。那么很直接的可以想到一种穷举的算法，即从左往右每一个位置都依此尝试填入一个数，看能不能填完这 n 个空格，在程序中我们可以用「回溯法」来模拟这个过程。
我们定义递归函数 backtrack(first,output) 表示从左往右填到第 first 个位置，当前排列为 output。 那么整个递归函数分为两个情况：
如果 first=n，说明我们已经填完了 n 个位置（注意下标从 0 开始），找到了一个可行的解，我们将 output 放入答案数组中，递归结束。 如果 first<n，我们要考虑这第 first 个位置我们要填哪个数。根据题目要求我们肯定不能填已经填过的数，因此很容易想到的一个处理手段是我们定义一个标记数组 vis 来标记已经填过的数，那么在填第 first 个数的时候我们遍历题目给定的 n 个数，如果这个数没有被标记过，我们就尝试填入，并将其标记，继续尝试填下一个位置，即调用函数 backtrack(first+1,output)。回溯的时候要撤销这一个位置填的数以及标记，并继续尝试其他没被标记过的数。 使用标记数组来处理填过的数是一个很直观的思路，但是可不可以去掉这个标记数组呢？毕竟标记数组也增加了我们算法的空间复杂度。
答案是可以的，我们可以将题目给定的 n 个数的数组 nums 划分成左右两个部分，左边的表示已经填过的数，右边表示待填的数，我们在回溯的时候只要动态维护这个数组即可。
具体来说，假设我们已经填到第 first 个位置，那么 nums 数组中 [0,first−1] 是已填过的数的集合，[first,n−1] 是待填的数的集合。我们肯定是尝试用 [first,n−1] 里的数去填第 first 个数，假设待填的数的下标为 iii，那么填完以后我们将第 i 个数和第 first 个数交换，即能使得在填第 first+1 个数的时候 nums 数组的 [0,first] 部分为已填过的数，[first+1,n−1] 为待填的数，回溯的时候交换回来即能完成撤销操作。
如果当前路径是 words 中的单词，则将其添加到结果集中。如果当前路径是 words 中任意一个单词的前缀，则继续搜索；反之，如果当前路径不是 words 中任意一个单词的前缀，则剪枝。我们可以将 words 中的所有字符串先添加到前缀树中，而后用 O(∣S∣) 的时间复杂度查询当前路径是否为 words 中任意一个单词的前缀。
在具体实现中，我们需要注意如下情况：
因为同一个单词可能在多个不同的路径中出现，所以我们需要使用哈希集合对结果集去重。
在回溯的过程中，我们不需要每一步都判断完整的当前路径是否是 words 中任意一个单词的前缀；而是可以记录下路径中每个单元格所对应的前缀树结点，每次只需要判断新增单元格的字母是否是上一个单元格对应前缀树结点的子结点即可。
public List<String> findWords(char[][] board, String[] words) { Trie trie = new Trie(); for (String word : words) { trie.insert(word); }
Set<String> ans = new HashSet<String>(); for (int i = 0; i < board.length; ++i) { for (int j = 0; j < board[0].length; ++j) { dfs(board, trie, i, j, ans); } }
return new ArrayList<String>(ans); }
public void dfs(char[][] board, Trie now, int i1, int j1, Set<String> ans) { if (!now.children.containsKey(board[i1][j1])) { return; } char ch = board[i1][j1]; now = now.children.get(ch); if (!"".equals(now.word)) { ans.add(now.word); }
class Trie { String word; Map<Character, Trie> children; boolean isWord;
public Trie() { this.word = ""; this.children = new HashMap<Character, Trie>(); }
public void insert(String word) { Trie cur = this; for (int i = 0; i < word.length(); ++i) { char c = word.charAt(i); if (!cur.children.containsKey(c)) { cur.children.put(c, new Trie()); } cur = cur.children.get(c); } cur.word = word; } }
void insertTrie(TrieNode * root,const string & word) { TrieNode * node = root; for (auto c : word){ if (!node->children.count(c)) { node->children[c] = new TrieNode(); } node = node->children[c]; } node->word = word; }
class Solution { public: int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
bool dfs(vector<vector<char>>& board, int x, int y, TrieNode * root, set<string> & res) { char ch = board[x][y]; if (!root->children.count(ch)) { return false; } root = root->children[ch]; if (root->word.size() > 0) { res.insert(root->word); }
board[x][y] = '#'; for (int i = 0; i < 4; ++i) { int nx = x + dirs[i][0]; int ny = y + dirs[i][1]; if (nx >= 0 && nx < board.size() && ny >= 0 && ny < board[0].size()) { if (board[nx][ny] != '#') { dfs(board, nx, ny, root,res); } } } board[x][y] = ch;
可以将棋盘抽象成一个包含 N^2^ 个节点的有向图，对于每个节点 x，若 x+i (1≤i≤6) 上没有蛇或梯子，则连一条从 x 到 x+i 的有向边；否则记蛇梯的目的地为 y，连一条从 x 到 y 的有向边。如此转换后，原问题等价于在这张有向图上求出从 1 到 N^2^ 的最短路长度。对于该问题，我们可以使用广度优先搜索。将节点编号和到达该节点的移动次数作为搜索状态，顺着该节点的出边扩展新状态，直至到达终点 N^2^ ，返回此时的移动次数。若无法到达终点则返回 −1。
代码实现时，我们可以用一个队列来存储搜索状态，初始时将起点状态 (1,0) 加入队列，表示当前位于起点 1，移动次数为 0。然后不断取出队首，每次取出队首元素时扩展新状态，即遍历该节点的出边，若出边对应节点未被访问，则将该节点和移动次数加一的结果作为新状态，加入队列。如此循环直至到达终点或队列为空。此外，我们需要计算出编号在棋盘中的对应行列，以便从 board 中得到目的地。设编号为 id，由于每行有 n 个数字，其位于棋盘从下往上数的第 $\dfrac{\textit{id}-1}{n} $ 行，记作 r。由于棋盘的每一行会交替方向，若 r 为偶数，则编号方向从左向右，列号为 (id−1) mod n；若 r 为奇数，则编号方向从右向左，列号为 n−1−((id−1) mod n)。
//C++ class Solution { pair<int, int> id2rc(int id, int n) { int r = (id - 1) / n, c = (id - 1) % n; if (r % 2 == 1) { c = n - 1 - c; } return {n - 1 - r, c}; }
public: int snakesAndLadders(vector<vector<int>> &board) { int n = board.size(); vector<int> vis(n * n + 1); queue<pair<int, int>> q; q.emplace(1, 0); while (!q.empty()) { auto p = q.front(); q.pop(); for (int i = 1; i <= 6; ++i) { int nxt = p.first + i; if (nxt > n * n) { // 超出边界 break; } auto rc = id2rc(nxt, n); // 得到下一步的行列 if (board[rc.first][rc.second] > 0) { // 存在蛇或梯子 nxt = board[rc.first][rc.second]; } if (nxt == n * n) { // 到达终点 return p.second + 1; } if (!vis[nxt]) { vis[nxt] = true; q.emplace(nxt, p.second + 1); // 扩展新状态 } } } return -1; } };
public int[] findOrder(int numCourses, int[][] prerequisites) { edges = new ArrayList<List<Integer>>(); for (int i = 0; i < numCourses; ++i) { edges.add(new ArrayList<Integer>()); } visited = new int[numCourses]; result = new int[numCourses]; index = numCourses - 1; for (int[] info : prerequisites) { edges.get(info[1]).add(info[0]); } // 每次挑选一个「未搜索」的节点，开始进行深度优先搜索 for (int i = 0; i < numCourses && valid; ++i) { if (visited[i] == 0) { dfs(i); } } if (!valid) { return new int[0]; } // 如果没有环，那么就有拓扑排序 return result; }
queue<int> q; // 将所有入度为 0 的节点放入队列中 for (int i = 0; i < numCourses; ++i) { if (indeg[i] == 0) { q.push(i); } }
while (!q.empty()) { // 从队首取出一个节点 int u = q.front(); q.pop(); // 放入答案中 result.push_back(u); for (int v: edges[u]) { --indeg[v]; // 如果相邻节点 v 的入度为 0，就可以选 v 对应的课程了 if (indeg[v] == 0) { q.push(v); } } }
//Java class Solution { // 存储有向图 List<List<Integer>> edges; // 存储每个节点的入度 int[] indeg; // 存储答案 int[] result; // 答案下标 int index;
public int[] findOrder(int numCourses, int[][] prerequisites) { edges = new ArrayList<List<Integer>>(); for (int i = 0; i < numCourses; ++i) { edges.add(new ArrayList<Integer>()); } indeg = new int[numCourses]; result = new int[numCourses]; index = 0; for (int[] info : prerequisites) { edges.get(info[1]).add(info[0]); ++indeg[info[0]]; }
Queue<Integer> queue = new LinkedList<Integer>(); // 将所有入度为 0 的节点放入队列中 for (int i = 0; i < numCourses; ++i) { if (indeg[i] == 0) { queue.offer(i); } }
while (!queue.isEmpty()) { // 从队首取出一个节点 int u = queue.poll(); // 放入答案中 result[index++] = u; for (int v: edges.get(u)) { --indeg[v]; // 如果相邻节点 v 的入度为 0，就可以选 v 对应的课程了 if (indeg[v] == 0) { queue.offer(v); } } }
if (index != numCourses) { return new int[0]; } return result; } }
复杂度分析
时间复杂度: O(n+m)，其中 n 为课程数，m 为先修课程的要求数。这其实就是对图进行广度优先搜索的时间复杂度。
