Trie-ді қолданатын ең ұзын префикс


Күрделілік дәрежесі қиын
Жиі кіреді Adobe Amazon алма Bloomberg еВау Facebook Google Microsoft
String ағаш Три

Ішінде Trie-ді қолданатын ең ұзын префикс біз жиынтығын ұсындық жолдар, ең ұзын префиксті табыңыз. яғни барлық жолдарға ортақ префикстің бөлігін табыңыз.

мысал

Input1: {“tutorialcup”, “tutorial”, “tussle”, “tumble”}
Output: "tu"

Input2: {"baggage", "banana", "batsmen"}
Output: "ba"

Input3: {"abcd"}
Output: "abcd"

Input4: {"customer","custard"}
Output: "cust"

Trie-ді қолданатын ең ұзын префикстің тәсілі

Мұндағы мақсат - үштік деректер құрылымын қолдану, оған барлық берілген жолдарды кірістіру, үштікті айналып өту және үштікте тармақталмай ең ұзын жол іздеу. Мұндай жол бойында алынған таңбалар біздің қажеттілігіміз ең ұзын префикс.

Trie-ді қолданатын ең ұзын префикстің алгоритмі

  1. Трие құрыңыз және барлық кіріс жолдарын триеге салыңыз. кірістіру () функциясы while жолдарының жиымынан жеке жолды кірістіру үшін қолданылады constructTrie () барлық енгізу жолдарын итеративті енгізу үшін қолданылады.
  2. ішіндегі ең ұзын префиксті сақтау префикс айнымалы.
  3. Енді триенің түбірлік түйінінен өтуді бастаңыз және келесі әрекеттерді орындаңыз:
    1. түйіннің жалғыз баласы бар-жоғын тексеріңіз. Оның баласы жоқ немесе біреуден көп баласы жоқ, травералды тоқтатады. Три түйінінің нөл емес балалар санын санау көмегімен жүзеге асырылады функция countChildren ().
    2. Егер түйінде жалғыз бала болса, сол балаға өтіп, сол түйінге сәйкес таңбаны префикске қосыңыз.
    3. баласы жоқ (немесе бірнеше баладан) түйін табылғанша 1 және 2 қадамдарды қайталаңыз or біз жолдар массивінде ең қысқа жолдың соңғы таңбасын сақтайтын үштік түйінге жетеміз. Қозғалыстың әр қадамы кезінде әрбір үш түйінге сәйкес таңбаны қосыңыз.
  4. 3-қадамда сипатталған траверсаль функцияны қолдану арқылы жүзеге асырылады walkTrie (), бұл функция үштікті айналып өтіп, ең кең таралған префикстің жолын іздейді және сәйкес ұзындықтағы префиксті қайтарады.
  5. Соңында біз драйвер функциясын қолданамыз longestCommonPrefix () жоғарыда аталған барлық функцияларды біріктіретін және берілген жолдар массивінің ішіндегі ең ұзын префиксті қайтаратын.

 

Trie-ді қолданатын ең ұзын префикс

Trie-ді қолданатын ең ұзын префикске арналған C ++ бағдарламасы

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

/* structure of a trie Node */
class TrieNode
{
    public:
    TrieNode *child[26];
    bool isEnd;
    
    TrieNode()
    {
        for(int i=0;i<26;i++)
        child[i] = NULL;
        
        isEnd = false;
    }
};

/* inserts a single string into a trie rooted at 'root' */
void insert(TrieNode *root, string key)
{
    TrieNode *temp = root;
    
    for(int i=0;i<key.length();i++)
    {
        int index = int(key[i] - 'a');
        
        if(temp->child[index] == NULL)
        temp->child[index] = new TrieNode();
        
        temp = temp->child[index];
    }
    
    temp->isEnd = true;
}

/* inserts an array of strings into the trie rooted at 'root' */
void constructTrie(TrieNode *root,vector <string> arr)
{
    for(int i=0;i<arr.size();i++)
    insert(root,arr[i]);
}

/* counts number of non NULL children a Trie Node has */
int countChildren(TrieNode *root,int &index)
{
    int count = 0;
    for(int i=0;i<26;i++)
    {
        if(root->child[i] != NULL)
        {
            count++;
            index = i;
        }
    }
    
    return count;
}

/* performs traversal on trie of strings rooted at 'root'
and returns the longest common prefix string */
string walkTrie(TrieNode *root)
{
    TrieNode *temp = root; 
    int index; 
    string prefix; 
  
    while (countChildren(temp, index) == 1 && temp->isEnd == false) 
    { 
        temp = temp->child[index]; 
        prefix.push_back('a'+index); 
    } 
    
    return prefix;
}

/* combines all the function above and return 
LCP among given array of strings */
string longestCommonPrefix(vector <string> arr)
{
    TrieNode *root = new TrieNode();
    constructTrie(root,arr);
    
    string prefix = walkTrie(root);
    
    return prefix;
}


int main()
{
    vector <string> arr = {"tutorialcup", "tutorial", "tussle", "tumble"};
    string ans = longestCommonPrefix(arr);
    
    if(ans.length())
    cout<<"Longest common prefix = "<<ans<<endl;
    else
    cout<<"No common prefix found"<<endl;
    
    return 0;
}
Longest common prefix = tu

Trie-ді қолданатын ең ұзын жалпы префикстің Java бағдарламасы

import java.io.*;
import java.util.*;

class tutorialCup
{
    /* structure of a trie Node */
    static class TrieNode
    {
        TrieNode[] child = new TrieNode[26];
        boolean isEnd;
        
        public TrieNode()
        {
            for(int i=0;i<26;i++)
            child[i] = null;
            
            isEnd = false;
        }
    };
    
    /* inserts a single string into a trie rooted at 'root' */
    static void insert(TrieNode root, String key)
    {
        TrieNode temp = root;
        
        for(int i=0;i<key.length();i++)
        {
            int index = key.charAt(i) - 'a';
            
            if(temp.child[index] == null)
            temp.child[index] = new TrieNode();
            
            temp = temp.child[index];
        }
        
        temp.isEnd = true;
    }
    
    /* inserts an array of strings into the trie rooted at 'root' */
    static void constructTrie(TrieNode root,ArrayList <String> arr)
    {
        for(int i=0;i<arr.size();i++)
        insert(root,arr.get(i));
    }
    
    static int index;
    
    /* counts number of non NULL children a Trie Node has */
    static int countChildren(TrieNode root)
    {
        int count = 0;
        for(int i=0;i<26;i++)
        {
            if(root.child[i] != null)
            {
                count++;
                index = i;
            }
        }
        
        return count;
    }
    
    /* performs traversal on trie of strings rooted at 'root'
    and returns the longest common prefix string */
    static StringBuffer walkTrie(TrieNode root)
    {
        TrieNode temp = root; 
        StringBuffer prefix = new StringBuffer(); 
      
        while (countChildren(temp) == 1 && temp.isEnd == false) 
        { 
            temp = temp.child[index]; 
            prefix.append((char)('a'+index)); 
        } 
        
        return prefix;
    }
    
    /* combines all the function above and return 
    LCP among given array of strings */
    static StringBuffer longestCommonPrefix(ArrayList <String> arr)
    {
        TrieNode root = new TrieNode();
        constructTrie(root,arr);
        
        StringBuffer prefix = walkTrie(root);
        
        return prefix;
    }
    
    public static void main (String[] args) 
    {
        ArrayList <String> arr = new ArrayList<>(Arrays.asList("tutorialcup", "tutorial", "tussle", "tumble"));
        StringBuffer ans = longestCommonPrefix(arr);
        
        if(ans.length() != 0)
        System.out.print("Longest common prefix = "+ans);
        else
        System.out.print("No common prefix found");
        
    }
}
Longest common prefix = tu

Күрделілікті талдау

  1. Уақыттың күрделілігі: T (n) = O (mn), қабылданған уақыттың жоғарғы шегі салу үштік.
  2. Кеңістіктің күрделілігі: A (n) = O (mn), кеңістіктің жоғарғы шекарасы жадта алады.

қайда,

n = ең ұзын жолдың ұзындығы

m = жол жиымындағы жолдар саны.

Әдебиеттер тізімі