360元网站建设,网站会员注册系统源码,php做直播网站,快优吧seo优化1. 题目
给出一个字符串数组words组成的一本英语词典。从中找出最长的一个单词#xff0c;该单词是由words词典中其他单词逐步添加一个字母组成。若其中有多个可行的答案#xff0c;则返回答案中字典序最小的单词。
若无答案#xff0c;则返回空字符串。
示例 1:
输入:
…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-next[i] 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(vectorstring 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(ia);//加入该字符if(temp.size() ans.size())ans temp;//更新更长的单词for(int j 0; j 26; j)dfs(root-next[j],temp,j);//dfs下一个字符temp.pop_back();//回溯}}
};
