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

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

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

#### 问题： ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][20200513200525454.png]

#### 思路： ####

###### 1.排序+哈希表 ######

考虑将排序后的字符串散列到unordered\_set中

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

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

###### 2.前缀树（字典树） ######

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

#### 代码： ####

###### 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;
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200513200504205.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw,size_16,color_FFFFFF,t_70
[20200513200525454.png]: https://img-blog.csdnimg.cn/20200513200525454.png
[Link 1]: https://blog.csdn.net/qq_44709990/article/details/106106131