一、面试问题给定一个大小为 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, vectorvectorchar 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; } // 主函数遍历网格所有起点查找单词 vectorvectorint searchWord(vectorvectorchar grid, string word) { int m grid.size(); // 网格行数 int n grid[0].size(); // 网格列数 vectorvectorint ans; // 存储所有有效起点坐标 // 8个方向向量对应 上、左上、右上、左、右、左下、右下、下 vectorint x { -1, -1, -1, 0, 0, 1, 1, 1 }; vectorint 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(vectorvectorint ans) { for (int i 0; i ans.size(); i) { cout { ans[i][0] , ans[i][1] } ; } cout endl; } int main() { // 测试用例网格 vectorvectorchar grid {{a,b,a,b}, {a,b,e,b}, {e,b,e,b}}; string word abe; // 要查找的单词 vectorvectorint 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; // 网格列数 Listint[] 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); // 网格列数 Listint[] ans new Listint[](); // 存储找到的起点坐标 // 定义 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(vectorvectorchar 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 个搜索方向 vectorintx { -1, -1, -1, 0, 0, 1, 1, 1 }; vectorinty { -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; } // 主函数遍历网格所有单元格调用查找函数 vectorvectorintsearchWord(vectorvectorchargrid, string word){ int m grid.size(); int n grid[0].size(); vectorvectorintans; // 存储所有匹配成功的起点 // 遍历每一个单元格 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(vectorvectorint ans) { for (int i0; ians.size(); i) { cout { ans[i][0] , ans[i][1] } ; } coutendl; } // 主测试函数 int main() { vectorvectorchar grid {{a,b,a,b},{a,b,e,b},{e,b,e,b}}; string word abe; vectorvectorint 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 Listint[] searchWord(char[][] grid, string word) { int m grid.Length; int n grid[0].Length; Listint[] ans new Listint[](); // 存储找到的起点坐标 // 遍历每一个单元格 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(Listint[] 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; // 要查找的单词 Listint[] 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)