一. 題目描述
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的方法，必定超時，leetcode筆記：Word Search II。
一種被廣為使用的方法是使用字典樹，網上的相關介紹不少，簡單沿用一種說法，就是一種單詞查找樹，Trie樹，屬于樹形結構，是一種哈希樹的變種。典型應用是用于統計，排序和保存大量的字符串（但不僅限于字符串），所以經常被搜索引擎系統用于文本詞頻統計。它的優點是：利用字符串的公共前綴來減少查詢時間，最大限度地減少無謂的字符串比較，查詢效率比哈希樹高。
其具體性質、查找方法等可參照：http://baike.baidu.com/link?url=BR1qdZ2oa8BIRbgtD6_oVsaBhzRecDJ0MMFntUvPGNjpG3XgJZihyUdFAlw1Pa30-OFUsNJRWPSanHng65l-Ja
而具體的解題思路是：
將待查找的單詞儲存在字典樹Trie中，使用DFS在board中查找，利用字典樹進行剪枝。 每當找到一個單詞時，將該單詞從字典樹中刪去。 返回結果按照字典序遞增排列。三. 示例代碼
以下代碼雖然使用字典樹來改進dfs，但AC后發現算法還是比較耗時：
<code class="hljs cpp">#include<iostream>#include<vector>#include<string>#include using namespace std;class TrieNode{public: TrieNode() // 構造函數 { 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，繼續遞歸插入 } 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); // 調用TrieNode類的方法 } 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); // 將候選單詞插入字典樹中 vector<string>result; for (int i = 0; i < x; ++i) { for (int j = 0; j < y; ++j) { // 用于記錄走過的路徑 vector<vector<b>> way(x, vector<b>(y, false)); dfs(board, way, "", i, j, result); } } // 以下操作排除重復出現的單詞 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>以下是網上一種使用字典樹的算法，耗時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>四. 小結
學習并初次使用了字典樹，并不是十分熟悉，寫出的代碼計算比較耗時，電腦資料《leetcode筆記：Word Search II》(https://www.unjs.com)。
这里有更多你想看的|
|
- 上一篇：電腦的工廠模式 電腦工廠模式是什么意思
- 下一篇：返回列表
