国家城乡建设规划部网站,建网站需求,廊坊建设公司网站,国外教程 网站1. 题目
给定一组单词words#xff0c;编写一个程序#xff0c;找出其中的最长单词#xff0c;且该单词由这组单词中的其他单词组合而成。 若有多个长度相同的结果#xff0c;返回其中字典序最小的一项#xff0c;若没有符合要求的单词则返回空字符串。
示例#xff1a…1. 题目
给定一组单词words编写一个程序找出其中的最长单词且该单词由这组单词中的其他单词组合而成。 若有多个长度相同的结果返回其中字典序最小的一项若没有符合要求的单词则返回空字符串。
示例
输入 [cat,banana,dog,nana,walk,walker,dogwalker]
输出 dogwalker
解释 dogwalker可由dog和walker组成。提示
0 len(words) 100
1 len(words[i]) 100来源力扣LeetCode 链接https://leetcode-cn.com/problems/longest-word-lcci 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
单词可重复使用先按长度降序排列长度相等字典序小的在前从前往后找到第一个单词即可将单词拆分成子串递归判断子串的子串
class Solution {
public:string longestWord(vectorstring words) {if(words.size() 2)return ;sort(words.begin(), words.end(),[](auto a, auto b){if(a.size() b.size())return a b;return a.size() b.size();});int i, len;string ans, sub;unordered_setstring set;for(i 0; i words.size(); i)set.insert(words[i]);for(i 0; i words.size()-1; i){for(len 1; len words[i].size(); len){sub words[i].substr(0,len);if(set.count(sub) ok(words[i].substr(len), set))return words[i];}}return ; }bool ok(string s, unordered_setstring set){if(s)return true;bool good false;for(int len 1; len s.size(); len){string sub s.substr(0,len);if(set.count(sub) ok(s.substr(len),set)){good true;break;}}return good;}
};48 ms 12.7 MB
