字典树：Leetcode 720:词典中最长的单词-蒲公英云

字典树：Leetcode 720:词典中最长的单词

r囧r小猫 2023-10-06 08:43 58阅读 0赞

字典树：Leetcode 720:词典中最长的单词

问题：

在这里插入图片描述

思路：

1.排序+哈希表

考虑将排序后的字符串散列到unordered_set中

对于排序后的输入，依次寻找字符串的子串是否在unordered_set中，首先子串中只包含第一个字符，随后子串增加第二个字符，以此类推，直至子串包含倒数第二个字符。若这些子串全都存在，则该字符串由词典中的单词组成，若此时该字符串长度也为满足条件的单词中最大的，则可以输出答案了，因此在排序中字符串长度长的应排在前面

由于题中要找出最长的单词，应改变排序策略，若两字符串长度相同，则应满足按字典序排列，若长度不同，长度更长的需排在前面，应对sort()函数提供排序函数，使得满足上述排序策略

2.前缀树（字典树）

前缀树文章在此
直接建立前缀树数据结构
依次将输入中的字符串插入到前缀树中
最长单词的每个字符在前缀树中对应的节点都能表示一个字符串
建立好前缀树后，在前缀树中依次查找输入中的字符串，若字符串中的每个字符都在前缀树中且都为完整字符串，则查找成功
在成功查找的字符串中选择最长串输出，若长度相同，选择字典序小的

代码：

1.排序+哈希表

class Solution {
public:
    static bool cmp( string &A,string &B )
    {
        return A.size()!=B.size()? A.size()>B.size() : A<B;
    }
    string longestWord(vector<string>& words) {
        unordered_set<string> table;
        sort( words.begin(),words.end(),cmp );
        for( string A:words )
            table.insert(A);
        int i;
        for( string A:words )
        {
            for( i=1;i<A.size();i++ )
            {
                if( table.find( A.substr( 0,i ) )==table.end() )
                    break;
            }
            if( i==A.size() )
                return A;
        }
        return "";
    }
};

2.前缀树

class Solution {
public:
    struct TrieNode
    {
        TrieNode* next[26];
        bool isStr;
    };
    void insert( TrieNode* root,string s )
    {
        TrieNode* location=root;
        int i=0;
        while( s[i] )
        {
            if( location->next[ s[i]-'a' ]==NULL )
            {
                TrieNode* newNode=new TrieNode();
                newNode->isStr=false;
                memset( newNode->next,NULL,sizeof(newNode->next) );
                location->next[ s[i]-'a' ]=newNode;
            }
            location=location->next[ s[i]-'a' ];
            i++;
        }
        location->isStr=true;
    }
    bool search( TrieNode* root,string s )
    {
        TrieNode* location=root;
        for(const auto& w:s){
            if(location->next[w-'a']==nullptr||location->next[w-'a']->isStr==false)return false;
            location=location->next[w-'a'];
        }
        return true;
    } 
    string longestWord(vector<string>& words) {
        TrieNode* root=new TrieNode();
        memset( root->next,NULL,sizeof(root->next) );
        for( string temp:words )
            insert( root,temp );
        string ans="";
        for( string temp:words )
        {
            if( search( root,temp ) )
            {
                if( temp.size()>ans.size() )
                    ans=temp;
                else if( temp.size()==ans.size() )
                {
                    if( temp<ans )
                        ans=temp;
                }
            }
        }
        return ans;
    }
};