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-1592:重新排列单词间的空格
leetcode-1592:重新排列单词间的空格
28 0
|
2天前
|
算法
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
|
3天前
|
算法
【经典LeetCode算法题目专栏分类】【第3期】回溯问题系列:单词搜索、N皇后问题、判断有效数独、解数独
【经典LeetCode算法题目专栏分类】【第3期】回溯问题系列:单词搜索、N皇后问题、判断有效数独、解数独
|
6天前
|
数据采集 机器学习/深度学习 算法
力扣79题:单词搜索
力扣79题:单词搜索
|
6天前
|
存储 SQL 算法
LeetCode题58: 5种算法实现最后一个单词的长度【python】
LeetCode题58: 5种算法实现最后一个单词的长度【python】
|
6天前
|
存储 算法 数据挖掘
LeetCode 题目 30:串联所有单词的子串【python】
LeetCode 题目 30:串联所有单词的子串【python】
|
10天前
|
算法 Java Go
【经典算法】LeetCode 58.最后一个单词的长度(Java/C/Python3/Go实现含注释说明,Easy)
【经典算法】LeetCode 58.最后一个单词的长度(Java/C/Python3/Go实现含注释说明,Easy)
11 0
|
10天前
|
存储 算法 Java
【经典算法】LeetCode 151. 反转字符串中的单词(Java/C/Python3实现含注释说明,中等)
【经典算法】LeetCode 151. 反转字符串中的单词(Java/C/Python3实现含注释说明,中等)
11 0
|
18天前
|
存储 C语言 容器
从C语言到C++_26(set+map+multiset+multimap)力扣692+349+牛客_单词识别(下)
从C语言到C++_26(set+map+multiset+multimap)力扣692+349+牛客_单词识别
23 1
|
18天前
|
存储 C语言 容器
从C语言到C++_26(set+map+multiset+multimap)力扣692+349+牛客_单词识别(中)
从C语言到C++_26(set+map+multiset+multimap)力扣692+349+牛客_单词识别
26 1