C++刷LeetCode（720. 词典中最长的单词）【字典树】【深度优先搜索】

糖逗

题目描述：

1. 给出一个字符串数组words组成的一本英语词典。从中找出最长的一个单词，该单词是由words词典中其他单词逐步添加一个字母组成。若其中有多个可行的答案，则返回答案中字典序最小的单词。
   
2. 
   
3. 若无答案，则返回空字符串。
   
4. 
   
5.  
   
6. 
   
7. 示例 1：
   
8. 
   
9. 输入：
   
10. words = ["w","wo","wor","worl", "world"]
    
11. 输出："world"
    
12. 解释：
    
13. 单词"world"可由"w", "wo", "wor", 和 "worl"添加一个字母组成。
    
14. 示例 2：
    
15. 
    
16. 输入：
    
17. words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
    
18. 输出："apple"
    
19. 解释：
    
20. "apply"和"apple"都能由词典中的单词组成。但是"apple"的字典序小于"apply"。
    
21.  
    
22. 
    
23. 提示：
    
24. 
    
25. 所有输入的字符串都只包含小写字母。
    
26. words数组长度范围为[1,1000]。
    
27. words[i]的长度范围为[1,30]。
    
28. 
    
29. 来源：力扣（LeetCode）
    
30. 链接：https://leetcode-cn.com/problems/longest-word-in-dictionary
    
31. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     struct TrieTree{
   
4.         bool flag;
   
5.         map<char, TrieTree*>next;
   
6.         TrieTree():flag(false){};
   
7.     };
   
8.     void dfs(TrieTree* cur_node, string&res, string temp){
   
9.         if(cur_node == NULL ||cur_node -> flag == false)return;
   
10.         if(temp.size() > res.size())res = temp;  
    
11.         for(auto cha : cur_node -> next){
    
12.             dfs(cur_node -> next[cha.first], res, temp + cha.first);
    
13.         }
    
14.     }
    
15.     string longestWord(vector<string>& words) {
    
16.         //构建字典树
    
17.         TrieTree* root = new TrieTree();
    
18.         for(auto word : words){
    
19.             TrieTree* node = root;
    
20.             for(auto cha : word){
    
21.                 if((node -> next).count(cha) == 0){
    
22.                     node -> next[cha] = new TrieTree();
    
23.                 }
    
24.                 node = node -> next[cha];
    
25.             }
    
26.             node -> flag = true;
    
27.         }
    
28.         //深度优先搜索
    
29.         string res;
    
30.         for(auto cha : root ->next){
    
31.             if(root -> next[cha.first] -> flag == true){
    
32.                 string temp;
    
33.                 dfs(root -> next[cha.first], res, temp + cha.first);
    
34.             }
    
35.         }
    
36.         return res;
    
37.     }
    
38. };

复制代码

糖逗