leetcode-720:词典中最长的单词

简介: leetcode-720:词典中最长的单词

题目

题目连接

给出一个字符串数组 words 组成的一本英语词典。返回 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" 

解题

方法一:字典树

  • 1.排序,按字符长度少的在前,如果相等,字典序小的在前
  • 2.如果长度为1的,直接插入trie;如果长度大于1的时候,满足长度l-1的字符也能在trie中找到,才能插入trie。
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){
            int l=word.size();
            if(l==1){
                if(l>maxSize){
                    maxSize=1;
                    res=word;
                }
                insert(word);//长度为1的时候都可以插入
                continue;
            }
            if(dfs(word.substr(0,l-1),0)){
                if(l>maxSize){
                    maxSize=l;
                    res=word;
                }
                insert(word);//长度大于1的时候,必须满足长度为l-1的能在字典树中找到
            }
        }
        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) return true;
        else 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; 
    }
};

写法二:

struct Trie{
    bool isEnd;
    vector<Trie*> next;
    Trie(){
        isEnd=false;
        next=vector<Trie*>(26,nullptr);
    }
};
class Solution {
public:
    Trie* trie=new Trie();
    void insert(string& s){
        Trie* node=trie;
        for(char c:s){
            if(!node->next[c-'a']) node->next[c-'a']=new Trie();
            node=node->next[c-'a'];
        }
        node->isEnd=true;
    }
    bool dfs(string& word){
        Trie* node=trie;
        for(int i=0;i<word.size()-1;i++){
            char c=word[i];
            if(node->next[c-'a']) node=node->next[c-'a'];
            else return false;
            if(node->isEnd==false) return false; 
        }
        return true;
    }
    string longestWord(vector<string>& words) {
        sort(words.begin(),words.end(),[](string& a,string& b){
            return a.size()<b.size();
        });
        string res;
        for(string& word:words){
            if(dfs(word)){
                if(word.size()>res.size()){
                    res=word;
                }else if(word.size()==res.size()&&word<res){
                    res=word;
                }
            }
            insert(word);
        }
        return res;
    }
};


相关文章
|
1月前
Leetcode(最后一个单词长度)
这篇文章介绍了两种解决LeetCode第58题的方法,即计算给定字符串中最后一个单词的长度,方法包括翻转字符串和逆向遍历统计。
19 0
|
1月前
【LeetCode 20】151.反转字符串里的单词
【LeetCode 20】151.反转字符串里的单词
19 0
|
3月前
|
算法
LeetCode第58题最后一个单词的长度
LeetCode第58题"最后一个单词的长度"的解题方法,通过从字符串末尾向前遍历并计数非空格字符,直接得出最后一个单词的长度。
LeetCode第58题最后一个单词的长度
|
3月前
|
算法 JavaScript Python
【Leetcode刷题Python】79. 单词搜索和剑指 Offer 12. 矩阵中的路径
Leetcode第79题"单词搜索"的Python解决方案,使用回溯算法在给定的二维字符网格中搜索单词,判断单词是否存在于网格中。
43 4
|
3月前
|
Python
【Leetcode刷题Python】生词本单词整理
文章提供了一个Python程序,用于帮助用户整理和排版生词本上的单词,包括去除重复单词、按字典序排序,并按照特定的格式要求进行打印排版。
41 3
|
3月前
|
Python
【Leetcode刷题Python】318. 最大单词长度乘积
本文提供了LeetCode题目318的Python编程解决方案,题目要求在一个字符串数组中找出两个不含有公共字母的单词,且这两个单词的长度乘积最大,如果不存在这样的两个单词,则返回0。
20 0
|
5月前
|
算法
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
|
5月前
|
存储 SQL 算法
LeetCode题58: 5种算法实现最后一个单词的长度【python】
LeetCode题58: 5种算法实现最后一个单词的长度【python】
|
5月前
|
算法 测试技术 索引
力扣经典150题第三十二题:串联所有单词的子串
力扣经典150题第三十二题:串联所有单词的子串
27 0
|
5月前
|
算法
力扣经典150题第二十一题:反转字符串中的单词
力扣经典150题第二十一题:反转字符串中的单词
60 0