Najdłuższy wspólny prefiks używający Trie

Poziom trudności Ciężko
Często zadawane pytania Adobe Amazonka Apple Bloomberg eBay Facebook Google Microsoft
sznur Drzewo sortujeodwiedzajacy 98

Pytania do rozmowy kwalifikacyjnej na temat projektowania systemu może być tak nieograniczona, że ​​trudno jest określić właściwy sposób przygotowania. Teraz jestem w stanie złamać rundy projektowe Amazon, Microsoft i Adobe po zakupie ta książka. Codziennie poprawiaj jeden pytanie projektowe i obiecuję, że możesz złamać cały projekt.

w Najdłuższy wspólny prefiks używający Trie problem, podaliśmy zestaw smyczkiznajdź najdłuższy wspólny prefiks. tzn. znajdź przedrostek, który jest wspólny dla wszystkich łańcuchów.

Przykład

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

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

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

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

Podejście do najdłuższego wspólnego prefiksu przy użyciu Trie

Chodzi o to, aby użyć struktury danych trie, wstawić do niej wszystkie podane ciągi, przejść przez próbę i wyszukać najdłuższą ścieżkę w trie bez rozgałęziania. Postacie zdobyte tą drogą są nam wymagane najdłuższy wspólny prefiks.

Algorytm dla najdłuższego wspólnego prefiksu przy użyciu Trie

  1. Skonstruuj próbę i wstaw do niej wszystkie ciągi wejściowe. wstawić() funkcja służy do wstawiania pojedynczego ciągu z podanej tablicy ciągów while constructTrie () służy do iteracyjnego wstawiania wszystkich ciągów wejściowych.
  2. przechowywać najdłuższy wspólny prefiks w prefiks zmienna.
  3. Teraz rozpocznij przemierzanie od węzła głównego próby i wykonaj następujące czynności:
    1. sprawdź, czy węzeł ma jedno dziecko, czy nie. Nie ma dziecka lub więcej niż jedno dziecko, kończy przechodzenie. Zliczanie liczby niepustych dzieci węzła trie odbywa się za pomocą funkcjonować countChildren ().
    2. Jeśli węzeł ma jedno dziecko, przejdź do tego dziecka i dołącz znak odpowiadający temu węzłowi do prefiksu.
    3. powtarzaj kroki 1 i 2, aż zostanie znaleziony węzeł bez dziecka (lub więcej niż jedno dziecko) or docieramy do węzła trie, który przechowuje ostatni znak najkrótszego ciągu w tablicy ciągów. Podczas każdego kroku przemierzania dodawaj znak odpowiadający każdemu węzłowi, przez który przeszedł.
  4. Przechodzenie opisane w kroku 3 jest realizowane za pomocą funkcji walkTrie (), ta funkcja przeszukuje trie i szuka najdłuższej wspólnej ścieżki prefiksu i zwraca odpowiadający jej najdłuższy wspólny prefiks.
  5. W końcu korzystamy z funkcji sterownika longestCommonPrefix () który łączy wszystkie wymienione powyżej funkcje i zwraca najdłuższy wspólny prefiks spośród podanej tablicy ciągów.

 

Najdłuższy wspólny prefiks używający Trieszpilka

Program C ++ dla najdłuższego wspólnego prefiksu przy użyciu Trie

#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

Program Java dla najdłuższego wspólnego prefiksu przy użyciu Trie

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

Analiza złożoności

  1. Złożoność czasowa: T (n) = O (mn), górna granica czasu potrzebnego do skonstruować próba.
  2. Złożoność przestrzeni: A (n) = O (mn), górna granica przestrzeni, którą trie zajmuje w pamięci.

gdzie,

n = długość najdłuższego łańcucha

m = liczba ciągów w tablicy ciągów.

Referencje

Wywiady dotyczące projektowania systemu pękania
Translate »