中级农民
- 积分
- 217
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2017-11-30
- 最后登录
- 1970-1-1
|
LC 212 Word Search II (class 3)
Problem Metrics:
1. Understand problem at 2 min
2. Get core concept at 3 min
3. Algorithm draft at 13 min
4. Detailed example derivation at 21 min
5. Code draft at 43 min
6. Code compile at 52 min
7. pass 33/37 test cases, TLE (code should be correct, just need more pruning) at 57 min
8. AC solution at 62 min (added a prefix table to simulate a trie)
Compile error:
ISO C++ forbids declaration of 'parameter' with no type [-fpermissive]
Reason: brackets "<>" don't match
When there are a lot of parameters in a function, make sure to handle everyone of them in the function call
Some backtracking is two-leveled, like this one, where the levels are handled differently. For this one, the first level is to iterate over all board starting locations, and this is done in the main function. The second level is the four-direction branching search, which is done in the recursive call. The key here is to know exactly where to modify the parent branch (in the branching loop), and where to check for results (in the base case/ending case checks before the branching loop)
Another take away:
Write down the thoughts as documentation as you think; lay out code structure in comments before actual coding.
Another take away 2:
A prefix table (eg. a hash table storing all possible prefixes for all valid words in a given dictionary) can be a quick hack if you want to use a trie but don't have the luxury to build one.
标准backtracking题目，这题作为hard的立足点在我看来是其代码的复杂性以及稍微对pruning有了一些要求。
C++代码如下：
class Solution {
public:
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
/* first, get all the words in a map for faster look up */
/* you need a state vector to keep track of visited cells;
the state vector will be modified along the way */
/* Use backtracking template */
/* Use a hashtable to handle duplicate valid words */
/* A trie will be much more helpful */
/* Naive ending case: search depth exceeds maximum word length */
/* Advanced ending case: current prefix doesn't exist in trie */
/* Note: finding a valid word is NOT an ending case here because this valid word
could be the prefix of a longer valid word, so you need to keep searching */
/* Each backtracking layer: branch and try next */
/* The difference here is that this is a two layer backtrack so you need to apply changes beforehand */
/* Step 1 preparation */
/* dictionary */
unordered_set<string> dictionary;
/* max word length used for ending case */
int maxLength = 0 ;
for(string word : words){
dictionary.emplace(word);
maxLength = max(maxLength, (int)word.size());
}
/* visited tracker */
vector<vector<bool> > visited(board.size(), vector<bool>(board[0].size(),false));
/* answer store */
unordered_set<string> answer;
/* handle the case of empty word */
if(dictionary.find("") != dictionary.end()){
answer.emplace("");
}
/* build a prefix table (to simulate a trie)*/
unordered_set<string> prefixes;
for(string word : words){
string prefix = "";
for(char c : word){
prefix += c;
prefixes.emplace(prefix);
}
}
string trackerStr = "";
/* Step 2 backtracking (this is the key step)*/
for(int i = 0; i < board.size(); ++i){
for(int j = 0; j < board[0].size(); ++j){
/* Apply changes */
visited[i][j] = true;
trackerStr += board[i][j];
/* Branch */
findWordsRecursion(board, dictionary, prefixes, &visited, maxLength, i, j, &trackerStr, &answer);
/* Undo changes */
trackerStr.pop_back();
visited[i][j] = false;
}
}
/* Step 3 generate and return answer */
vector<string> answerVector;
for(auto itr = answer.begin(); itr != answer.end(); ++itr){
answerVector.emplace_back(*itr);
}
return answerVector;
}
void findWordsRecursion(const vector<vector<char> > & board,
const unordered_set<string> & dictionary,
const unordered_set<string> & prefixes,
vector<vector<bool> > * visited,
int maxLength, int i, int j,
string * trackerStr,
unordered_set<string> * answer){
/* Ending case handling (do return) */
if(trackerStr->size() > maxLength)return;
if(prefixes.find(*trackerStr) == prefixes.end())return;
// cout << trackerStr->size() << " " << *trackerStr << endl;
/* Base case handling (don't return ) */
if(dictionary.find(*trackerStr) != dictionary.end()){
answer->emplace(*trackerStr);
}
/* branching, four directions */
if(i > 0){
if((*visited)[i-1][j] == false){
(*visited)[i-1][j] = true;
(*trackerStr) += board[i-1][j];
findWordsRecursion(board, dictionary, prefixes, visited, maxLength, i - 1, j, trackerStr, answer);
(*visited)[i-1][j] = false;
trackerStr->pop_back();
}
}
if(i < board.size()-1){
if((*visited)[i+1][j] == false){
(*visited)[i+1][j] = true;
(*trackerStr) += board[i+1][j];
findWordsRecursion(board, dictionary, prefixes, visited, maxLength, i + 1, j, trackerStr, answer);
(*visited)[i+1][j] = false;
trackerStr->pop_back();
}
}
if(j > 0){
if((*visited)[i][j-1] == false){
(*visited)[i][j-1] = true;
(*trackerStr) += board[i][j-1];
findWordsRecursion(board, dictionary, prefixes, visited, maxLength, i, j - 1, trackerStr, answer);
(*visited)[i][j-1] = false;
trackerStr->pop_back();
}
}
if(j < board[0].size()-1){
if((*visited)[i][j+1] == false){
(*visited)[i][j+1] = true;
(*trackerStr) += board[i][j+1];
findWordsRecursion(board, dictionary, prefixes, visited, maxLength, i, j + 1, trackerStr, answer);
(*visited)[i][j+1] = false;
trackerStr->pop_back();
}
}
}
};
|
|
楼主: 大木虫
狗仔卡
楼主
