生活随笔
收集整理的这篇文章主要介绍了
LeetCode 212. 单词搜索 II（Trie树+DFS）
小编觉得挺不错的,现在分享给大家,帮大家做个参考.
1. 题目
给定一个二维网格 board 和一个字典中的单词列表 words，找出所有同时在二维网格和字典中出现的单词。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。
示例:
输入:
words = ["oath","pea","eat","rain"] and board =
[['o','a','a','n'],['e','t','a','e'],['i','h','k','r'],['i','f','l','v']
]
输出: ["eat","oath"]
说明:
你可以假设所有输入都由小写字母 a-z 组成。
类似题目：LeetCode 79. 单词搜索（回溯DFS）
2. Trie树+DFS
- 先将单词插入Trie树
- 再遍历board中的每个字符，以每个字符为起点DFS在Trie中查找
class TrieNode
{
public:string str
;TrieNode
*next
[26];bool isEnd
;TrieNode():isEnd(false) {memset(next
, 0, sizeof(TrieNode
*)*26);}
};
class Trie
{
public:TrieNode
*root
;Trie(){root
= new TrieNode();}~Trie(){destroy(root
);}void destroy(TrieNode
*root
){if(root
== NULL)return;for(int i
= 0; i
< 26; i
++)destroy(root
->next
[i
]);delete root
;}void insert(string word
){TrieNode
*cur
= root
;for(char s
:word
){if(cur
->next
[s
-'a'] == NULL)cur
->next
[s
-'a'] = new TrieNode();cur
= cur
->next
[s
-'a'];}cur
->isEnd
= true;cur
->str
= word
;}
};class Solution {Trie tree
;
public:vector
<string
> findWords(vector
<vector
<char>>& board
, vector
<string
>& words
) {for(auto word
: words
)tree
.insert(word
);int i
, j
;vector
<string
> ans
;for(i
= 0; i
< board
.size(); ++i
)for(j
= 0; j
< board
[0].size(); ++j
)dfs(board
,tree
.root
,i
,j
,ans
);return ans
;}void dfs(vector
<vector
<char>>& b
, TrieNode
*cur
, int x
, int y
, vector
<string
> &ans
){if(cur
->isEnd
){cur
->isEnd
= false;ans
.push_back(cur
->str
);return;}if(x
< 0 || x
== b
.size() || y
< 0 || y
== b
[0].size()) return;if(b
[x
][y
] == '#' || !cur
|| (b
[x
][y
] != '#' && cur
->next
[b
[x
][y
]-'a'] == NULL))return;char ch
= b
[x
][y
];cur
= cur
->next
[ch
-'a'];b
[x
][y
] = '#'; dfs(b
,cur
,x
+1,y
,ans
);dfs(b
,cur
,x
-1,y
,ans
);dfs(b
,cur
,x
,y
+1,ans
);dfs(b
,cur
,x
,y
-1,ans
);b
[x
][y
] = ch
; }
};
总结
以上是生活随笔为你收集整理的LeetCode 212. 单词搜索 II（Trie树+DFS）的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
