敬请期待海报_上海免费网站建设模板_网站seo哪家公司好_网络营销的主要内容包括

1 题目：单词搜索 II

官方标定难度：难

给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words， 返回所有二维网格上的单词 。

单词必须按照字母顺序，通过 相邻的单元格 内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。

示例 1：

输入：board = [[“o”,“a”,“a”,“n”],[“e”,“t”,“a”,“e”],[“i”,“h”,“k”,“r”],[“i”,“f”,“l”,“v”]], words = [“oath”,“pea”,“eat”,“rain”]
输出：[“eat”,“oath”]

示例 2：

输入：board = [[“a”,“b”],[“c”,“d”]], words = [“abcb”]
输出：[]

提示：

m == board.length
n == board[i].length
1 <= m, n <= 12
board[i][j] 是一个小写英文字母
$1<=words.length<=3\ast 10^4$
1 <= words[i].length <= 10
words[i] 由小写英文字母组成
words 中的所有字符串互不相同

2 solution

本题是在题 单词搜索 I 的基础上进行了拓展，需要在递归的同时进行快速单词前缀的检索。可以利用前缀树（字典树）来做，主要思路是将所有单词存储在一棵树上，每个字母为一个节点，前缀相同的单词共享前缀节点。优点是快速查找单词和前缀，缺点是比较消耗内存。

代码

class Trie {struct Node {int end = -1, path = 0;Node *child[26]{};};unordered_set<string> set;Node *root;vector<string> &words;vector<vector<char>> &board;vector<int> dx;vector<int> dy;int n, m;vector<vector<bool>> vis;
public:vector<string> res;Trie(vector<string> &words, vector<vector<char>> &board) : words(words), board(board) {root = new Node;dx = {0, 0, 1, -1};dy = {1, -1, 0, 0};m = board.size();n = board[0].size();vis = vector<vector<bool>>(m, vector<bool>(n));addWords();for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(root->child[board[i][j] - 'a'])dfs(i, j, root->child[board[i][j] - 'a']);}}}void addWord(string &word, int k) {Node *cur = root;for (int i = 0; i < word.size(); i++) {int idx = word[i] - 'a';if (!cur->child[idx]) {cur->child[idx] = new Node();}cur->path++;cur = cur->child[idx];}cur->end = k;cur->path++;}void addWords() {for (int i = 0; i < words.size(); i++) {addWord(words[i], i);}}void dfs(int x, int y, Node *node) {if (!node) return;if (node->end >= 0) {if(set.count(words[node->end]) == 0){res.push_back(words[node->end]);set.insert(words[node->end]);}}vis[x][y] = true;for (int i = 0; i < 4; i++) {int xx = x + dx[i];int yy = y + dy[i];if (xx < 0 || xx >= m || yy < 0 || yy >= n) continue;if (vis[xx][yy]) continue;int idx = board[xx][yy] - 'a';dfs(xx, yy, node->child[idx]);}vis[x][y] = false;}};class Solution {
public:vector<string> findWords(vector<vector<char>> &board, vector<string> &words) {Trie trie(words, board);return trie.res;}
};

结果