1

## 【小馬的LeetCode練功坊】leetcode教你解字謎遊戲- 79. Word Search，212. Word Search II

(見wiki- Word search)

``````board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.
``````

# 79. c++程式(AC)

``````class Solution {
public:
bool inBoundary(vector<vector<char>>&board,int pr,int pc){
return pr>=0 && pr<board.size() && pc>=0 && pc<board[0].size();
}

bool dfs(vector<vector<char>>&board,int pr,int pc,string &word,int count){
if(count==word.size()-1){
return true;
}
char temp=board[pr][pc];
board[pr][pc]='.';
vector<pair<int, int>> directions = {{1,0}, {-1,0}, {0,1}, {0,-1}}; //定義四個方向
for(auto d: directions){
int r = pr+d.first, c = pc+d.second;
if(inBoundary(board, r, c) && board[r][c]==word[count+1]&&dfs(board,r,c,word,count+1)){
return true;
}
}
board[pr][pc] = temp;
return false;

}

bool exist(vector<vector<char>>& board, string word) {

for(int i=0;i<board.size();i++){
for(int j=0;j<board[0].size();j++){
if(board[i][j]==word[0] && dfs(board,i,j,word,0)){
return true;
}
}
}
return false;
}
};
``````

# 字謎搜索多個單字

``````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"]
``````

# 212. c++程式(超時)

``````class Solution {
public:

bool inBoundary(vector<vector<char>>&board,int pr,int pc){
return pr>=0 && pr<board.size() && pc>=0 && pc<board[0].size();
}

bool dfs(vector<vector<char>>&board,int pr,int pc,string &word,int count){
if(count==word.size()-1){
return true;
}
char temp=board[pr][pc];
board[pr][pc]='.';
vector<pair<int, int>> directions = {{1,0}, {-1,0}, {0,1}, {0,-1}}; //定義四個方向
for(auto d: directions){
int r = pr+d.first, c = pc+d.second;
if(inBoundary(board, r, c) && board[r][c]==word[count+1]&&dfs(board,r,c,word,count+1)){
board[pr][pc] = temp;
return true;
}
}
board[pr][pc] = temp;
return false;

}

bool exist(vector<vector<char>>& board, string word) {

for(int i=0;i<board.size();i++){
for(int j=0;j<board[0].size();j++){
if(board[i][j]==word[0] && dfs(board,i,j,word,0)){
return true;
}
}
}
return false;

}
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
vector<string> res;
for(string word: words){
if(exist(board, word)){
res.push_back(word);
}
}
return res;
}
};
``````

# 212. c++程式(AC)

``````class Solution {
class TrieNode {
public:
vector<TrieNode *> child; //子節點有a~z共26種可能，初始設為null
string prefix; //若某點為單字的結尾，記錄該字的prefix
TrieNode(): prefix(""), child(vector<TrieNode *>(26, NULL)) {};
};

class Trie {
public:
TrieNode* root; //root為一個空的節點
/** Initialize your data structure here. */
Trie(): root(new TrieNode()) {};

/** Inserts a word into the trie. */
void insert(string word) {
TrieNode *p = root;
for (char c : word) {
int i = c - 'a';
if (!p->child[i]){
p->child[i] = new TrieNode();
}
p = p->child[i];
}
p->prefix = word;
}
};
public:

bool inBoundary(vector<vector<char>>&board,int pr,int pc){
return pr>=0 && pr<board.size() && pc>=0 && pc<board[0].size();
}

void dfs(vector<vector<char>>&board, TrieNode* trie, int pr,int pc, vector<string> &res){
if(!trie->prefix.empty()){
res.push_back(trie->prefix);
trie->prefix = ""; //避免同一個字重複加到res裡
}
char temp=board[pr][pc];
board[pr][pc]='.';
vector<pair<int, int>> directions = {{1,0}, {-1,0}, {0,1}, {0,-1}}; //定義四個方向
for(auto d: directions){
int r = pr+d.first, c = pc+d.second;
if(inBoundary(board, r, c) && board[r][c]!='.' && trie->child[board[r][c] - 'a']){
dfs(board, trie->child[board[r][c] - 'a'], r, c, res);
}
}
board[pr][pc] = temp;

}

vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
vector<string> res;
Trie wordTrie;
for(string word: words){
wordTrie.insert(word);
}
for(int i=0;i<board.size();i++){
for(int j=0;j<board[0].size();j++){
if (wordTrie.root->child[board[i][j] - 'a']) {
dfs(board, wordTrie.root->child[board[i][j] - 'a'], i, j, res);
}
}
}
return res;
}
};
``````