leetcode-面试题 17.15：最长单词

leetcode-面试题 17.15：最长单词

• 题目
• 解题
• • 方法一：字典树+dfs

题目

题目连接

给定一组单词words，编写一个程序，找出其中的最长单词，且该单词由这组单词中的其他单词组合而成。若有多个长度相同的结果，返回其中字典序最小的一项，若没有符合要求的单词则返回空字符串。

示例：

输入： ["cat","banana","dog","nana","walk","walker","dogwalker"]
输出： "dogwalker"
解释： "dogwalker"可由"dog"和"walker"组成。

解题

方法一：字典树+dfs

首先排序，长度小的放前面，如果长度相等，字典序小的放前面。
如果从头开始遍历，因为相同长度，字典序小的会取到。

class Trie{
public:bool isEnd=false;vector<Trie*> next=vector<Trie*>(26,nullptr);
};class Solution {
public:Trie* trie=new Trie();string longestWord(vector<string>& words) {sort(words.begin(),words.end(),[](string& a,string& b){if(a.size()==b.size()) return a<b;//如果长度相等，字典序小的放前面return a.size()<b.size();//长度小的放前面});int maxSize=0;string res="";for(string& word:words){if(dfs(word,0)){if(word.size()>maxSize){maxSize=word.size();res=word;}}else insert(word);}return res;}bool dfs(string& word,int startIndex){if(startIndex==word.size()) return true;Trie* node=trie;for(int i=startIndex;i<word.size();i++){char c=word[i];if(node->next[c-'a']){node=node->next[c-'a'];}else return false;if(node->isEnd){if(dfs(word,i+1)) return true;}}return false;}void insert(string& word){Trie* node=trie;for(char c:word){if(node->next[c-'a']==nullptr){node->next[c-'a']=new Trie();}node=node->next[c-'a'];}node->isEnd=true;}
};

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！