LeetCode 720. 词典中最长的单词（Trie树）

Michael阿明

发布于 2020-07-13 16:04:44

7570

发布于 2020-07-13 16:04:44

文章被收录于专栏：Michael阿明学习之路Michael阿明学习之路

1. 题目

给出一个字符串数组words组成的一本英语词典。从中找出最长的一个单词，该单词是由words词典中其他单词逐步添加一个字母组成。若其中有多个可行的答案，则返回答案中字典序最小的单词。

若无答案，则返回空字符串。

示例 1:
输入: 
words = ["w","wo","wor","worl", "world"]
输出: "world"
解释: 
单词"world"可由"w", "wo", "wor", 和 "worl"添加一个字母组成。

示例 2:
输入: 
words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
输出: "apple"
解释: 
"apply"和"apple"都能由词典中的单词组成。但是"apple"得字典序小于"apply"。

注意:
所有输入的字符串都只包含小写字母。
words数组长度范围为[1,1000]。
words[i]的长度范围为[1,30]。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/longest-word-in-dictionary

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. Trie树解题

题目意思：从1个字母开始，每次增加一个字母（包含原始字母在内的每一步组成的单词都必须在字典中找的到），最终形成的最长单词是谁

对所有的单词，插入Trie树
对每个 root->nexti i=[0,26)，进行dfs搜索查找最长的单词

Trie树结构参考

class Trie//Trie节点
{
public:
	bool isWord;
	Trie* next[26] = {NULL};
	Trie():isWord(false){}	
};

class Solution {
	string ans;
public:
    string longestWord(vector<string>& words) {
    	Trie *root = new Trie();
    	Trie *cur;
       	for(string str : words)//遍历所有单词
       	{
       		cur = root;
       		for(char ch : str)//遍历所有字符
       		{
       			if(cur->next[ch-'a'] == NULL)
       				cur->next[ch-'a'] = new Trie();
       			cur = cur->next[ch-'a'];
       		}
       		cur->isWord = true;//单词结束标志
       	}
       	string temp;
       	cur = root;
       	int i, j;
       	for(i = 0; i < 26; ++i)
       	{
       		temp = "";
       		if(cur->next[i] && cur->next[i]->isWord)//对每个点dfs	
       			dfs(cur->next[i], temp, i);
       	}
       	return ans;
    }

    void dfs(Trie* root, string &temp, int i)
    {
    	if(!root)
    		return;
    	if(root->isWord)//是结束标志，在字典中
    	{
    		temp.push_back(i+'a');//加入该字符
    		if(temp.size() > ans.size())
       			ans = temp;//更新更长的单词
    		for(int j = 0; j < 26; ++j)
    			dfs(root->next[j],temp,j);//dfs下一个字符
    		temp.pop_back();//回溯
    	}
    }
};