福州云建站模版天津百度推广网络科技公司

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

思路一：回溯

bool sub_exist(char** board, int row, int col, char* word, int y, int x){if(*word == '\0')  return true;if(y < 0 || y >= row || x < 0 || x >= col || *word != board[y][x]return false;board[y][x] = '\0';  bool result = sub_exist(board, row, col, word + 1, y + 1, x) ||sub_exist(board, row, col, word + 1, y - 1, x) ||sub_exist(board, row, col, word + 1, y, x + 1) ||sub_exist(board, row, col, word + 1, y, x - 1) ;board[y][x] = *word;        return result;
}bool exist(char** board, int boardSize, int* boardColSize, char* word){for(int y = 0; y < boardSize; y ++){for(int x = 0; x < boardColSize[0]; x ++){if(board[y][x] == word[0] && sub_exist(board, boardSize, boardColSize[0], word, y, x))return true;}}return false;         
}

分析：

本题问字符串是否在字符网中，可使用回溯算法，判断每一个字母前后左右是否有下一个字符，若没有或者到达边界即返回false，不断递归判断是否有匹配字符最后返回true或false

总结：

本题考察回溯算法的应用，注意递归的方向有前后左右四个方向。