题目链接：点击打开链接
题目大意：略
解题思路：略
相关企业
- 字节跳动
- 亚马逊（Amazon）
- 微软（Microsoft）
- 推特（Twitter）
- 彭博（Bloomberg）
- 优步（Uber）
- 思科（Cisco）
- 谷歌（Google）
- 苹果（Apple）
AC 代码
- Java
// 解决方案(1) class Solution { // 使用 Map 超时 // private Map<Integer, Boolean> usedMap = new HashMap<>(); private boolean ok = false; private boolean[][] path; public boolean exist(char[][] board, String word) { path = new boolean[board.length][board[0].length]; for (int i = 0; i < board.length; i++) { for (int j = 0; j < board[i].length; j++) { if (ok) { return true; } // usedMap.clear(); // 不需要每次都初始化, 比较耗时, 因为回溯的时候会恢复到原始状态 // path = new boolean[board.length][board[0].length]; handle(board, i, j, word, 0); } } return ok; } private void handle(char[][] board, int i, int j, String word, int ptr) { if (ok || i >= board.length || i < 0 || j >= board[0].length || j < 0) { return; } // Integer key = i * 10 + j; if (path[i][j]) { return; } if (board[i][j] == word.charAt(ptr)) { if (ptr + 1 >= word.length()) { ok = true; return; } path[i][j] = true; // usedMap.put(key, true); handle(board, i + 1, j, word, ptr + 1); handle(board, i - 1, j, word, ptr + 1); handle(board, i, j + 1, word, ptr + 1); handle(board, i, j - 1, word, ptr + 1); // usedMap.remove(key); path[i][j] = false; } } } // 解决方案(2) class Solution { public boolean exist(char[][] board, String word) { char[] words = word.toCharArray(); for(int i = 0; i < board.length; i++) { for(int j = 0; j < board[0].length; j++) { if(dfs(board, words, i, j, 0)) return true; } } return false; } boolean dfs(char[][] board, char[] word, int i, int j, int k) { if(i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != word[k]) return false; if(k == word.length - 1) return true; board[i][j] = '\0'; boolean res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) || dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i , j - 1, k + 1); board[i][j] = word[k]; return res; } }
- C++
class Solution { public: bool exist(vector<vector<char>>& board, string word) { rows = board.size(); cols = board[0].size(); for(int i = 0; i < rows; i++) { for(int j = 0; j < cols; j++) { if(dfs(board, word, i, j, 0)) return true; } } return false; } private: int rows, cols; bool dfs(vector<vector<char>>& board, string word, int i, int j, int k) { if(i >= rows || i < 0 || j >= cols || j < 0 || board[i][j] != word[k]) return false; if(k == word.size() - 1) return true; board[i][j] = '\0'; bool res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) || dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i , j - 1, k + 1); board[i][j] = word[k]; return res; } };
