LeetCode|LeetCode第79题--单词搜索 LeetCode|递归回溯|算法编程学习

给定一个二维网格和一个单词，找出该单词是否存在于网格中。
【LeetCode|LeetCode第79题--单词搜索】单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
board =
[
[‘A’,‘B’,‘C’,‘E’],
[‘S’,‘F’,‘C’,‘S’],
[‘A’,‘D’,‘E’,‘E’]
]
给定 word = “ABCCED”, 返回 true.
给定 word = “SEE”, 返回 true.
给定 word = “ABCB”, 返回 false.

class Solution { bool dfs(vector>& board, vector> &useLetter, string word, int index, int row, int col) { int rowSize = board.size(); int colSize = board[0].size(); if(index >= word.length()) return true; if(row-1 >= 0 && useLetter[row-1][col] == false && word[index] == board[row-1][col]) { useLetter[row-1][col] = true; if(dfs(board, useLetter, word, index+1, row-1, col)) return true; useLetter[row-1][col] = false; } if(row+1 < rowSize && useLetter[row+1][col] == false && word[index] == board[row+1][col]) { useLetter[row+1][col] = true; //注意此处不能直接return dfs(board, useLetter, word, index+1, row+1, col)； if(dfs(board, useLetter, word, index+1, row+1, col)) return true; useLetter[row+1][col] = false; } if(col-1 >= 0 && useLetter[row][col-1] == false && word[index] == board[row][col-1]) { useLetter[row][col-1] = true; if(dfs(board, useLetter, word, index+1, row, col-1)) return true; useLetter[row][col-1] = false; } if(col+1 < colSize && useLetter[row][col+1] == false && word[index] == board[row][col+1]) { useLetter[row][col+1] = true; if(dfs(board, useLetter, word, index+1, row, col+1)) return true; useLetter[row][col+1] = false; } return false; }public: bool exist(vector>& board, string word) { if(board.size() == 0 || board[0].size() == 0 || word == "") return false; int rowSize = board.size(); int colSize = board[0].size(); vector> useLetter(rowSize, vector(colSize, false)); for(int i = 0; i < rowSize; i++) { for(int j = 0; j < colSize; j++) { if(board[i][j] == word[0])//先找到第一个匹配的字母。 { useLetter[i][j] = true; if(dfs(board, useLetter, word, 1, i, j)) return true; useLetter[i][j] = false; } } } return false; } };

理解深度优先遍历之后，该题并不难，原理同“解数独”类似，使用一个useLetter判断该字母是否被找到。