一、面试问题
给定一个大小为 m×n 的二维字符网格和一个单词，任务是找出该单词在网格中的所有出现位置。单词可以在任意位置沿8 个方向进行匹配。只有当沿某一方向所有字符都依次匹配时，才算找到该单词（非曲折形式）。
8 个方向分别为：水平向左、水平向右、垂直向上、垂直向下，以及 4 个对角线方向。
注意：返回的列表应按字典序最小排列。如果从同一坐标出发沿多个方向均可找到该单词，列表中该坐标只需出现一次。
示例 1：
- 输入以下矩阵：
grid = { {G,E,E,K,S,F,O,R,G,E,E,K,S}, {G,E,E,K,S,Q,U,I,Z,G,E,E,K}, {I,D,E,Q,A,P,R,A,C,T,I,C,E} } word = "GEEKS"- 得到以下输出：
{ {0,0}, {0,8}, {1,0} }- 解释如下：
示例 2：
- 输入以下矩阵：
grid = {{a,b,a,b},{a,b,e,b},{e,b,e,b}} word = "abe"- 得到以下输出：
{ {0,0}, {0,2}, {1,0} }- 解释如下：
二、【朴素解法】使用递归 —— 时间复杂度 O (m*n*k)，空间复杂度 O (k)
(一) 解法思路
遍历网格中的每个单元格，并在8 个方向（上、下、左、右、四个对角线）上检查是否能找到目标单词。对于每个单元格，我们只沿着选定的一个方向继续匹配。
我们持续检查：
- 沿着选定方向移动时，网格中的字符是否与目标单词的字符依次匹配。
- 如果成功匹配完整单词，就记录下起始坐标。
- 我们对网格中的每一个单元格递归执行上述操作。
(二) 使用 5 种语言实现
1. C++
// C++ program to search a word in a 2D grid #include <bits/stdc++.h> using namespace std; // 检查坐标 (x,y) 是否在网格有效范围内 bool validCoord(int x, int y, int m, int n) { if (x >= 0 && x < m && y >= 0 && y < n) return true; return false; } // 递归函数：从 (x,y) 开始，沿 (dirX, dirY) 方向查找单词 // index：当前要匹配的单词字符下标 bool findWord(int index, string word, vector<vector<char>> &grid, int x, int y, int dirX, int dirY) { // 递归终止条件：所有字符都匹配完成，找到单词 if (index == word.length()) return true; // 坐标有效 + 当前字符匹配 → 继续沿同一方向递归匹配下一个字符 if (validCoord(x, y, grid.size(), grid[0].size()) && word[index] == grid[x][y]) return findWord(index + 1, word, grid, x + dirX, y + dirY, dirX, dirY); // 坐标越界 或 字符不匹配 → 查找失败 return false; } // 主函数：遍历网格所有起点，查找单词 vector<vector<int>> searchWord(vector<vector<char>> grid, string word) { int m = grid.size(); // 网格行数 int n = grid[0].size(); // 网格列数 vector<vector<int>> ans; // 存储所有有效起点坐标 // 8个方向向量：对应 上、左上、右上、左、右、左下、右下、下 vector<int> x = { -1, -1, -1, 0, 0, 1, 1, 1 }; vector<int> y = { -1, 0, 1, -1, 1, -1, 0, 1 }; // 遍历网格每一个单元格作为起点 for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ // 尝试8个方向查找 for (int k = 0; k < 8; k++) { // 任意一个方向找到单词 → 记录起点，不再检查其他方向 if (findWord(0, word, grid, i, j, x[k], y[k])) { ans.push_back({i, j}); break; } } } } return ans; } // 打印结果 void printResult(vector<vector<int>> ans) { for (int i = 0; i < ans.size(); i++) { cout << "{" << ans[i][0] << "," << ans[i][1] << "}" << " "; } cout << endl; } int main() { // 测试用例网格 vector<vector<char>> grid = {{'a','b','a','b'}, {'a','b','e','b'}, {'e','b','e','b'}}; string word = "abe"; // 要查找的单词 vector<vector<int>> ans = searchWord(grid, word); printResult(ans); // 输出结果 }2. Java
// Java 程序：在二维字符网格中查找单词（8个方向，递归实现） import java.util.*; class DSA { // 检查坐标 (x, y) 是否在网格有效范围内 static boolean validCoord(int x, int y, int m, int n) { if (x >= 0 && x < m && y >= 0 && y < n) return true; return false; } // 递归函数：从 (x,y) 出发，沿固定方向 (dirX, dirY) 查找单词 // index：当前需要匹配的单词字符下标 static boolean findWord(int index, String word, char[][] grid, int x, int y, int dirX, int dirY) { // 递归终止条件：所有字符匹配完成，找到单词 if (index == word.length()) return true; // 如果坐标有效，且当前字符匹配 → 继续沿同一方向匹配下一个字符 if (validCoord(x, y, grid.length, grid[0].length) && word.charAt(index) == grid[x][y]) return findWord(index + 1, word, grid, x + dirX, y + dirY, dirX, dirY); // 越界或字符不匹配 → 查找失败 return false; } // 主函数：遍历所有起点，8个方向查找单词 static int[][] searchWord(char[][] grid, String word) { int m = grid.length; // 网格行数 int n = grid[0].length; // 网格列数 List<int[]> ans = new ArrayList<>(); // 存储找到的起点坐标 // 定义 8 个搜索方向 int[] x = { -1, -1, -1, 0, 0, 1, 1, 1 }; int[] y = { -1, 0, 1, -1, 1, -1, 0, 1 }; // 遍历网格每一个单元格作为起点 for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { // 尝试 8 个方向 for (int k = 0; k < 8; k++) { // 只要任意一个方向找到单词，就记录起点并跳出 if (findWord(0, word, grid, i, j, x[k], y[k])) { ans.add(new int[] { i, j }); break; } } } } // 把列表转为二维数组返回 return ans.toArray(new int[0][]); } // 打印结果 static void printResult(int[][] ans) { for (int[] a : ans) { System.out.print("{" + a[0] + "," + a[1] + "}" + " "); } System.out.println(); } public static void main(String[] args) { // 测试网格 char[][] grid = { { 'a', 'b', 'a', 'b' }, { 'a', 'b', 'e', 'b' }, { 'e', 'b', 'e', 'b' } }; String word = "abe"; // 要查找的单词 int[][] ans = searchWord(grid, word); printResult(ans); // 输出结果 } }3. Python
# Python 程序：在二维字符网格中查找单词（8个方向，递归实现） # 检查坐标 (x, y) 是否在网格有效范围内 def isValid(x, y, sizeX, sizeY): return 0 <= x < sizeX and 0 <= y < sizeY # 递归函数：从 (x,y) 出发，沿固定方向 (dirX, dirY) 查找单词 # index：当前要匹配的单词字符下标 def findWordInDirection(grid, n, m, word, index, x, y, dirX, dirY): # 递归终止：所有字符匹配完成，找到单词 if index == len(word): return True # 坐标有效 + 字符匹配 → 继续沿同一方向匹配下一个字符 if isValid(x, y, n, m) and word[index] == grid[x][y]: return findWordInDirection(grid, n, m, word, index + 1, x + dirX, y + dirY, dirX, dirY) # 越界或不匹配 → 查找失败 return False # 主函数：遍历所有起点，8个方向查找单词 def searchWord(grid, word): ans = [] # 存储找到的起点坐标 n = len(grid) # 行数 m = len(grid[0]) # 列数 # 定义 8 个搜索方向 directions = [(1, 0), (-1, 0), # 下、上 (0, 1), (0, -1), # 右、左 (1, 1), (1, -1), # 右下、左下 (-1, 1), (-1, -1)]# 左上、右上 # 遍历每一个单元格 for i in range(n): for j in range(m): # 只有首字符匹配时，才开始方向查找 if grid[i][j] == word[0]: for dirX, dirY in directions: # 任意一个方向找到 → 记录起点，不再检查其他方向 if findWordInDirection(grid, n, m, word, 0, i, j, dirX, dirY): ans.append([i, j]) break return ans # 打印结果 def printResult(ans): for a in ans: print(f"{{{a[0]},{a[1]}}}", end=" ") print() # 测试代码 if __name__ == "__main__": grid = [['a', 'b', 'a', 'b'], ['a', 'b', 'e', 'b'], ['e', 'b', 'e', 'b']] word = "abe" ans = searchWord(grid, word) printResult(ans)4. C#
// C# 程序：在二维字符网格中查找单词（8个方向，递归实现） using System; using System.Collections.Generic; class DSA { // 检查坐标 (x, y) 是否在网格有效范围内 static bool validCoord(int x, int y, int m, int n) { if (x >= 0 && x < m && y >= 0 && y < n) return true; return false; } // 递归函数：从 (x,y) 出发，沿固定方向 (dirX, dirY) 查找单词 // index：当前需要匹配的单词字符下标 static bool findWord(int index, string word, char[,] grid, int x, int y, int dirX, int dirY) { // 递归终止条件：所有字符匹配完成，找到单词 if (index == word.Length) return true; // 如果坐标有效，且当前字符匹配 → 继续沿同一方向匹配下一个字符 if (validCoord(x, y, grid.GetLength(0), grid.GetLength(1)) && word[index] == grid[x, y]) return findWord(index + 1, word, grid, x + dirX, y + dirY, dirX, dirY); // 越界或字符不匹配 → 查找失败 return false; } // 主函数：遍历所有起点，8个方向查找单词 static int[][] searchWord(char[,] grid, string word) { int m = grid.GetLength(0); // 网格行数 int n = grid.GetLength(1); // 网格列数 List<int[]> ans = new List<int[]>(); // 存储找到的起点坐标 // 定义 8 个搜索方向 int[] x = { -1, -1, -1, 0, 0, 1, 1, 1 }; int[] y = { -1, 0, 1, -1, 1, -1, 0, 1 }; // 遍历网格每一个单元格作为起点 for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { // 尝试 8 个方向 for (int k = 0; k < 8; k++) { // 只要任意一个方向找到单词，就记录起点并跳出 if (findWord(0, word, grid, i, j, x[k], y[k])) { ans.Add(new int[] { i, j }); break; } } } } // 把列表转为二维数组返回 return ans.ToArray(); } // 打印结果 static void printResult(int[][] ans) { foreach (var a in ans) { Console.Write("{" + a[0] + "," + a[1] + "}" + " "); } Console.WriteLine(); } static void Main() { // 测试网格 char[,] grid = { { 'a', 'b', 'a', 'b' }, { 'a', 'b', 'e', 'b' }, { 'e', 'b', 'e', 'b' } }; string word = "abe"; // 要查找的单词 int[][] ans = searchWord(grid, word); printResult(ans); // 输出结果 } }5. JavaScript
// JavaScript 程序：二维字符网格中查找单词（8个方向 · 递归实现） // 检查坐标 (x, y) 是否在网格有效范围内 function validCoord(x, y, m, n) { return (x >= 0 && x < m && y >= 0 && y < n); } // 递归函数：从 (x,y) 出发，沿固定方向 (dirX, dirY) 查找单词 // index：当前要匹配的单词字符下标 function findWord(index, word, grid, x, y, dirX, dirY) { // 递归终止：所有字符匹配完成，成功找到单词 if (index === word.length) return true; // 坐标有效 + 当前字符匹配 → 继续沿同一方向匹配下一个字符 if (validCoord(x, y, grid.length, grid[0].length) && word[index] === grid[x][y]) return findWord(index + 1, word, grid, x + dirX, y + dirY, dirX, dirY); // 越界 或 字符不匹配 → 查找失败 return false; } // 主函数：遍历所有起点，8个方向查找单词 function searchWord(grid, word) { let m = grid.length; // 网格行数 let n = grid[0].length; // 网格列数 let ans = []; // 存储所有有效起点坐标 // 定义 8 个搜索方向 let x = [-1, -1, -1, 0, 0, 1, 1, 1]; let y = [-1, 0, 1, -1, 1, -1, 0, 1]; // 遍历网格每一个单元格作为起点 for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { // 尝试 8 个方向 for (let k = 0; k < 8; k++) { // 任意一个方向找到单词 → 记录起点，不再检查其他方向 if (findWord(0, word, grid, i, j, x[k], y[k])) { ans.push([i, j]); break; } } } } return ans; } // 打印结果 function printResult(ans) { for (let i = 0; i < ans.length; i++) { console.log("{" + ans[i][0] + "," + ans[i][1] + "}"); } } // 测试用例 const grid = [ ['a', 'b', 'a', 'b'], ['a', 'b', 'e', 'b'], ['e', 'b', 'e', 'b'] ]; const word = "abe"; const ans = searchWord(grid, word); printResult(ans);(三)代码输出和算法复杂度
输出：
{0,0} {0,2} {1,0}时间复杂度：O(m*n*k)
空间复杂度：O(k)
三、【最优解法】使用迭代法（非递归）实现 —— 时间 O (m*n*k)，空间 O (1)
(一) 解法思路
这是对上面递归方法的迭代实现版本。在这里，我们对每个单元格，沿着一个方向迭代地向前移动，而不是使用递归。
我们不断检查：
- 沿着选定方向移动时，网格中的字符是否与单词依次匹配。
- 如果完整匹配到整个单词，就记录这个起点。
- 我们对网格中的每一个单元格都执行这一过程。
(二) 使用 5 种语言实现
1. C++
// C++ program to search a word in a 2D grid #include <bits/stdc++.h> using namespace std; // 迭代函数：从 (row, col) 出发，在 8 个方向中迭代查找单词 bool search2D(vector<vector<char>> grid, int row, int col, string word) { int m = grid.size(); // 网格行数 int n = grid[0].size(); // 网格列数 // 如果起点字符和单词首字符不匹配，直接返回 false if (grid[row][col] != word[0]) return false; int len = word.size(); // 单词长度 // 定义 8 个搜索方向 vector<int>x = { -1, -1, -1, 0, 0, 1, 1, 1 }; vector<int>y = { -1, 0, 1, -1, 1, -1, 0, 1 }; // 遍历 8 个方向，逐个查找 for (int dir = 0; dir < 8; dir++) { // 从起点的下一个字符开始匹配 int k, currX = row + x[dir], currY = col + y[dir]; // 首字符已匹配，迭代匹配剩余所有字符 for (k = 1; k < len; k++) { // 坐标越界，直接退出当前方向 if (currX >= m || currX < 0 || currY >= n || currY < 0) break; // 字符不匹配，退出当前方向 if (grid[currX][currY] != word[k]) break; // 沿当前方向继续移动 currX += x[dir], currY += y[dir]; } // 如果 k == 单词长度，说明完整匹配成功 if (k == len) return true; } // 所有方向都未匹配成功 return false; } // 主函数：遍历网格所有单元格，调用查找函数 vector<vector<int>>searchWord(vector<vector<char>>grid, string word){ int m = grid.size(); int n = grid[0].size(); vector<vector<int>>ans; // 存储所有匹配成功的起点 // 遍历每一个单元格 for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ // 如果从 (i,j) 能找到单词，加入结果集 if(search2D(grid, i, j, word)){ ans.push_back({i, j}); } } } return ans; } // 打印结果 void printResult(vector<vector<int>> ans) { for (int i=0; i<ans.size(); i++) { cout << "{" << ans[i][0] << "," << ans[i][1] << "}" << " "; } cout<<endl; } // 主测试函数 int main() { vector<vector<char>> grid = {{'a','b','a','b'},{'a','b','e','b'},{'e','b','e','b'}}; string word = "abe"; vector<vector<int>> ans = searchWord(grid, word); printResult(ans); }2. Java
// Java 程序：在二维网格中沿8个方向查找单词（迭代实现） import java.util.*; class DSA { // 迭代函数：从 (row, col) 出发，在8个方向中查找单词 static boolean search2D(char[][] grid, int row, int col,String word) { int m = grid.length; // 网格行数 int n = grid[0].length; // 网格列数 // 如果起点字符与单词首字符不匹配，直接返回false if (grid[row][col] != word.charAt(0)) return false; int len = word.length(); // 单词长度 // 定义8个搜索方向 int[] x = { -1, -1, -1, 0, 0, 1, 1, 1 }; int[] y = { -1, 0, 1, -1, 1, -1, 0, 1 }; // 遍历所有8个方向 for (int dir = 0; dir < 8; dir++) { int k, currX = row + x[dir], currY = col + y[dir]; // 首字符已匹配，迭代匹配剩余字符 for (k = 1; k < len; k++) { // 坐标越界，退出当前方向 if (currX >= m || currX < 0 || currY >= n || currY < 0) break; // 字符不匹配，退出当前方向 if (grid[currX][currY] != word.charAt(k)) break; // 沿当前方向继续移动 currX += x[dir]; currY += y[dir]; } // 所有字符都匹配成功 if (k == len) return true; } // 所有方向均未找到 return false; } // 主函数：遍历网格所有单元格，查找单词 static int[][] searchWord(char[][] grid, String word) { int m = grid.length; int n = grid[0].length; // 最大可能出现次数 int[][] ans = new int[m * n][2]; int count = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { // 找到单词，记录坐标 if (search2D(grid, i, j, word)) { ans[count][0] = i; ans[count][1] = j; count++; } } } // 调整数组大小，仅保留有效结果 int[][] result = new int[count][2]; for (int i = 0; i < count; i++) { result[i] = ans[i]; } return result; } // 打印结果 static void printResult(int[][] ans) { for (int[] coords : ans) { System.out.print("{" + coords[0] + "," + coords[1] + "}" + " "); } System.out.println(); } public static void main(String[] args) { // 测试网格 char[][] grid = { { 'a', 'b', 'a', 'b' }, { 'a', 'b', 'e', 'b' }, { 'e', 'b', 'e', 'b' } }; String word = "abe"; int[][] ans = searchWord(grid, word); printResult(ans); } }3. Python
# Python 程序：在二维字符网格中沿8个方向查找单词（迭代实现） # 迭代查找函数：从 (row, col) 出发，遍历8个方向，直线匹配单词 def search2D(grid, row, col, word): m = len(grid) # 网格行数 n = len(grid[0]) # 网格列数 # 如果起点字符与单词首字符不匹配，直接返回 False if grid[row][col] != word[0]: return False lenWord = len(word) # 单词长度 # 定义 8 个搜索方向 x = [-1, -1, -1, 0, 0, 1, 1, 1] y = [-1, 0, 1, -1, 1, -1, 0, 1] # 遍历 8 个方向，逐个尝试 for dir in range(8): # 从起点的下一个位置开始，沿当前方向移动 currX, currY = row + x[dir], col + y[dir] k = 1 # 已匹配第 0 个字符，从第 1 个开始匹配 # 迭代匹配剩余字符 while k < lenWord: # 坐标越界 → 退出当前方向 if currX >= m or currX < 0 or currY >= n or currY < 0: break # 字符不匹配 → 退出当前方向 if grid[currX][currY] != word[k]: break # 沿当前方向继续前进一步 currX += x[dir] currY += y[dir] k += 1 # 如果 k == 单词长度 → 完整匹配成功 if k == lenWord: return True # 所有方向都未找到单词 return False # 主函数：遍历网格所有单元格，调用查找函数 def searchWord(grid, word): m = len(grid) n = len(grid[0]) ans = [] # 存储所有找到的起点坐标 # 遍历每一个单元格 for i in range(m): for j in range(n): # 如果从 (i,j) 能找到单词，加入结果 if search2D(grid, i, j, word): ans.append((i, j)) return ans # 打印结果 def printResult(ans): for coord in ans: print(f"{{{coord[0]},{coord[1]}}}", end=" ") print() # 测试主程序 if __name__ == "__main__": grid = [['a', 'b', 'a', 'b'], ['a', 'b', 'e', 'b'], ['e', 'b', 'e', 'b']] word = "abe" ans = searchWord(grid, word) printResult(ans)4. C#
// C# 程序：在二维网格中沿8个方向查找单词（迭代实现） using System; using System.Collections.Generic; class DSA { // 迭代函数：从 (row, col) 出发，在8个方向中查找单词 static bool search2D(char[][] grid, int row, int col, string word) { int m = grid.Length; // 网格行数 int n = grid[0].Length; // 网格列数 // 如果起点字符与单词首字符不匹配，直接返回 false if (grid[row][col] != word[0]) return false; int len = word.Length; // 单词长度 // 定义 8 个搜索方向 int[] x = { -1, -1, -1, 0, 0, 1, 1, 1 }; int[] y = { -1, 0, 1, -1, 1, -1, 0, 1 }; // 遍历 8 个方向，逐个尝试查找 for (int dir = 0; dir < 8; dir++) { // 从起点的下一个位置开始，沿当前方向移动 int k, currX = row + x[dir], currY = col + y[dir]; // 首字符已匹配，迭代匹配剩余字符 for (k = 1; k < len; k++) { // 坐标越界 → 退出当前方向 if (currX >= m || currX < 0 || currY >= n || currY < 0) break; // 字符不匹配 → 退出当前方向 if (grid[currX][currY] != word[k]) break; // 沿当前方向继续前进一步 currX += x[dir]; currY += y[dir]; } // 如果 k == 单词长度 → 完整匹配成功 if (k == len) return true; } // 所有方向均未找到单词 return false; } // 主函数：遍历网格所有单元格，查找单词 static List<int[]> searchWord(char[][] grid, string word) { int m = grid.Length; int n = grid[0].Length; List<int[]> ans = new List<int[]>(); // 存储找到的起点坐标 // 遍历每一个单元格 for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { // 找到单词，记录坐标 if (search2D(grid, i, j, word)) { ans.Add(new int[] { i, j }); } } } return ans; } // 打印结果 static void printResult(List<int[]> ans) { foreach (var coord in ans) { Console.Write("{" + coord[0] + "," + coord[1] + "}" + " "); } Console.WriteLine(); } static void Main() { // 测试用网格 char[][] grid = new char[][] { new char[] { 'a', 'b', 'a', 'b' }, new char[] { 'a', 'b', 'e', 'b' }, new char[] { 'e', 'b', 'e', 'b' } }; string word = "abe"; // 要查找的单词 List<int[]> ans = searchWord(grid, word); printResult(ans); // 输出结果 } }5. JavaScript
// JavaScript 程序：在二维网格中沿8个方向查找单词（迭代实现） // 迭代函数：从 (row, col) 出发，在8个方向中查找单词 function search2D(grid, row, col, word) { let m = grid.length; // 网格行数 let n = grid[0].length; // 网格列数 // 如果起点字符与单词首字符不匹配，直接返回 false if (grid[row][col] !== word[0]) return false; let len = word.length; // 单词长度 // 定义 8 个搜索方向 let x = [-1, -1, -1, 0, 0, 1, 1, 1]; let y = [-1, 0, 1, -1, 1, -1, 0, 1]; // 遍历 8 个方向，逐个尝试查找 for (let dir = 0; dir < 8; dir++) { // 从起点的下一个位置开始，沿当前方向移动 let currX = row + x[dir], currY = col + y[dir], k = 1; // 首字符已匹配，迭代匹配剩余字符 for (k = 1; k < len; k++) { // 坐标越界 → 退出当前方向 if (currX >= m || currX < 0 || currY >= n || currY < 0) break; // 字符不匹配 → 退出当前方向 if (grid[currX][currY] !== word[k]) break; // 沿当前方向继续前进一步 currX += x[dir]; currY += y[dir]; } // 如果 k === 单词长度 → 完整匹配成功 if (k === len) return true; } // 所有方向均未找到单词 return false; } // 主函数：遍历网格所有单元格，查找单词 function searchWord(grid, word) { let m = grid.length; let n = grid[0].length; let ans = []; // 存储找到的起点坐标 // 遍历每一个单元格 for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { // 找到单词，记录坐标 if (search2D(grid, i, j, word)) { ans.push([i, j]); } } } return ans; } // 打印结果 function printResult(ans) { ans.forEach(coord => { console.log("{" + coord[0] + "," + coord[1] + "}"); }); } // 测试用例 let grid = [ ['a', 'b', 'a', 'b'], ['a', 'b', 'e', 'b'], ['e', 'b', 'e', 'b'] ]; let word = "abe"; // 要查找的单词 let ans = searchWord(grid, word); printResult(ans); // 输出结果(三)代码输出和算法复杂度
输出：
{0,0} {0,2} {1,0}时间复杂度：O(m*n*k)
空间复杂度：O(1)
