题目描述
Given a 2D board and a list of words from the dictionary, find all words in the board.
Each word must be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.
Example1:
Input: board = [ ['o','a','a','n'], ['e','t','a','e'], ['i','h','k','r'], ['i','f','l','v'] ] words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]
NOTE
- All inputs are consist of lowercase letters a-z.
- The values of words are distinct.
解题思路
- 最简单的dfs
- 会报超时
class Solution {
public:
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
vector<string> res;
int row = board.size();
if(row == 0){
return res;
}
int col = board[0].size();
bool isVisit[row * col];
unordered_set<string> sets;
for(int i = 0; i < words.size(); i++){
for(int j = 0; j < row * col; j++){
isVisit[j] = false;
}
for(int j = 0; j < row; j++){
for(int k = 0; k < col; k++){
if(dfs(j, k, row, col, board, 0, words[i], isVisit)){
if(sets.count(words[i]) == 0){
res.push_back(words[i]);
sets.insert(words[i]);
break;
}
}
}
}
}
return res;
}
bool dfs(int r, int c, int row, int col, vector<vector<char>>& board, int len, string str, bool* isVisit){
if(len == str.size()){
return true;
}
if(r < 0 || r >= row || c < 0 || c >= col || isVisit[r * col + c] == true || board[r][c] != str[len]){
return false;
}
isVisit[r * col + c] = true;
if(dfs(r + 1, c, row, col, board, len + 1, str, isVisit) ||
dfs(r - 1, c, row, col, board, len + 1, str, isVisit) ||
dfs(r, c + 1, row, col, board, len + 1, str, isVisit) ||
dfs(r, c - 1, row, col, board, len + 1, str, isVisit)){
return true;
}
isVisit[r * col + c] = false;
return false;
}
};
- 用前缀树来做
- 先把单词插入到前缀树中
- 然后遍历这个board，从头开始，看是否能够遍历到
- 参考
