一. 題目描述
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.
For example,
Given words =["oath","pea","eat","rain"]and board =
<code class="hljs json">[ ['o','a','a','n'], ['e','t','a','e'], ['i','h','k','r'], ['i','f','l','v']]</code>
Return["eat","oath"].
Note:
You may assume that all inputs are consist of lowercase lettersa-z.
二. 題目分析
若沿用Word Search的方法，必定超時(shí)，
leetcode筆記：Word Search II
。一種被廣為使用的方法是使用字典樹(shù)，網(wǎng)上的相關(guān)介紹不少，簡(jiǎn)單沿用一種說(shuō)法，就是一種單詞查找樹(shù)，Trie樹(shù)，屬于樹(shù)形結(jié)構(gòu)，是一種哈希樹(shù)的變種。典型應(yīng)用是用于統(tǒng)計(jì)，排序和保存大量的字符串（但不僅限于字符串），所以經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計(jì)。它的優(yōu)點(diǎn)是：利用字符串的公共前綴來(lái)減少查詢(xún)時(shí)間，最大限度地減少無(wú)謂的字符串比較，查詢(xún)效率比哈希樹(shù)高。
其具體性質(zhì)、查找方法等可參照：http://baike.baidu.com/link?url=BR1qdZ2oa8BIRbgtD6_oVsaBhzRecDJ0MMFntUvPGNjpG3XgJZihyUdFAlw1Pa30-OFUsNJRWPSanHng65l-Ja
而具體的解題思路是：
將待查找的單詞儲(chǔ)存在字典樹(shù)Trie中，使用DFS在board中查找，利用字典樹(shù)進(jìn)行剪枝。 每當(dāng)找到一個(gè)單詞時(shí)，將該單詞從字典樹(shù)中刪去。 返回結(jié)果按照字典序遞增排列。三. 示例代碼
以下代碼雖然使用字典樹(shù)來(lái)改進(jìn)dfs，但AC后發(fā)現(xiàn)算法還是比較耗時(shí)：
<code class="hljs cpp">#include<iostream>#include<vector>#include<string>#include using namespace std;class TrieNode{public: TrieNode() // 構(gòu)造函數(shù) { for (int i = 0; i < 26; ++i) next[i] = NULL; end = false; } void insert(string s) { if (s.empty()) { end = true; return; } if (next[s[0] - 'a'] == NULL) next[s[0] - 'a'] = new TrieNode(); next[s[0] - 'a']->insert(s.substr(1)); // 右移一位截取字符串s，繼續(xù)遞歸插入 } bool search(string key) { if (key.empty()) return end; if (next[key[0] - 'a'] == NULL) return false; return next[key[0] - 'a']->search(key.substr(1)); } bool startsWith(string prefix) { if (prefix.empty()) return true; if (next[prefix[0] - 'a'] == NULL) return false; return next[prefix[0] - 'a']->startsWith(prefix.substr(1)); }private: TrieNode *next[26]; bool end;};class Tri{public: Tri(){ root = new TrieNode(); } void insert(string s) { root->insert(s); // 調(diào)用TrieNode類(lèi)的方法 } bool search(string k) { return root->search(k); } bool startsWith(string p) { return root->startsWith(p); }private: TrieNode *root;};class Solution{public: vector<string>findWords(vector<vector<char>>& board, vector<string>& words) { const int x = board.size(); const int y = board[0].size(); for (auto ptr : words) tree.insert(ptr); // 將候選單詞插入字典樹(shù)中 vector<string>result; for (int i = 0; i < x; ++i) { for (int j = 0; j < y; ++j) { // 用于記錄走過(guò)的路徑 vector<vector<b>> way(x, vector<b>(y, false)); dfs(board, way, "", i, j, result); } } // 以下操作排除重復(fù)出現(xiàn)的單詞 sort(result.begin(), result.end()); result.erase(unique(result.begin(), result.end()), result.end()); return result; }private: Tri tree; void dfs(vector<vector<char>> &board, vector<vector<b>> way, string word, int x, int y, vector<string>&result) { if (x < 0 || x >= board.size() || y < 0 || y >= board[0].size()) // 超出邊界 return; if (way[x][y]) return; word.push_back(board[x][y]); if (tree.search(word)) result.push_back(word); if (tree.startsWith(word)) { way[x][y] = true; dfs(board, way, word, x + 1, y, result); dfs(board, way, word, x - 1, y, result); dfs(board, way, word, x, y + 1, result); dfs(board, way, word, x, y - 1, result); way[x][y] = false; } word.pop_back(); }};</string></vector<b></vector<char></bool></vector<b></string></string></vector<char></string></string></vector></iostream></code>以下是網(wǎng)上一種使用字典樹(shù)的算法，耗時(shí)48ms - 56ms：
<code class="hljs cpp">class Trie { public: Trie *next[26]; bool exist; Trie() { fill_n(next, 26, nullptr); exist = false; } ~Trie() { for (int i = 0; i < 26; ++i) delete next[i]; } void insert(const string &t) { Trie *iter = this; for (int i = 0; i < t.size(); ++i) { if (iter->next[t[i] - 'a'] == nullptr) iter->next[t[i] - 'a'] = new Trie(); iter = iter->next[t[i] - 'a']; } iter->exist = true; }};class Solution { public: int m, n; vector<string>findWords(vector<vector<char>>& board, vector<string>& words) { Trie *trie = new Trie(); for (auto &s : words) trie->insert(s); m = board.size(); n = board[0].size(); vector<string>ret; string sofar; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { bc(board, ret, sofar, trie, i, j); } } return ret; } void bc(vector<vector<char>> &board, vector<string>&ret, string &sofar, Trie *root, int x, int y) { if (x < 0 || y < 0 || x >= m || y >= n || board[x][y] == '\0' || root == nullptr) return ; if (root->next[board[x][y] - 'a'] == nullptr) return ; root = root->next[board[x][y] - 'a']; char t = '\0'; swap(t, board[x][y]); sofar.push_back(t); if (root->exist) { root->exist = false; ret.push_back(sofar); } bc(board, ret, sofar, root, x, y + 1); bc(board, ret, sofar, root, x + 1, y); bc(board, ret, sofar, root, x - 1, y); bc(board, ret, sofar, root, x, y - 1); swap(t, board[x][y]); sofar.pop_back(); }};</string></vector<char></string></string></vector<char></string></code>四. 小結(jié)
學(xué)習(xí)并初次使用了字典樹(shù)，并不是十分熟悉，寫(xiě)出的代碼計(jì)算比較耗時(shí)，