Trie istifadə edilən ən uzun ümumi prefiks

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur Çiy kərpic Amazon alma Bloomberg eBay Facebook google microsoft
Sim Ağac cəhd edinBaxılıb 98

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Ci Trie istifadə edilən ən uzun ümumi prefiks problem bir sıra verdik strings, ən uzun yayılmış prefiksi tapın. yəni bütün strings üçün ümumi olan prefiks hissəsini tapın.

misal

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

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

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

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

Trie istifadə edərək ən uzun yayılmış prefiks üçün yanaşma

Fikir bir trie məlumat quruluşundan istifadə etmək, verilən bütün simləri içərisinə daxil etmək, üçlüyü aşmaq və üçdə budaqlanmadan ən uzun yolu axtarmaqdır. Belə bir yol boyunca əldə olunan simvollar bizim tələbimizdir ən uzun yayılmış prefiks.

Trie istifadə edərək ən uzun yayılmış prefiks üçün alqoritm

  1. Üçlüyü qurun və bütün giriş simlərini üçlüyə daxil edin. daxil etmək () funksiyası isə verilən sətirlərdən fərdi bir sətir əlavə etmək üçün istifadə olunur qurmaqTrie () bütün giriş sətirlərini təkrarlamaq üçün istifadə olunur.
  2. ən uzun yayılmış prefiksi prefiks dəyişən.
  3. İndi, trienin kök düyünündən bir hərəkətə başlayın və aşağıdakıları edin:
    1. düyünün tək övladı olub olmadığını yoxlayın. Çocuğu yoxdur və ya birdən çox uşağı var, keçidi dayandırır. Üçlü bir düyünün boş olmayan uşaqlarının sayını istifadə edərək edilir funksiyası countChildren ().
    2. Düyünün tək bir uşağı varsa, həmin uşağa keçin və həmin düyünə uyğun xarakteri prefiksə əlavə edin.
    3. uşağı olmayan (və ya birdən çox uşağı olmayan) bir qovşaq tapılana qədər 1 və 2-ci addımları təkrarlayın or simlər massivində ən qısa sətrin son simvolunu saxlayan bir trie noduna çatırıq. Keçidin hər bir mərhələsi boyunca, hər bir üç node qovşağına uyğun bir simvol əlavə etməyə davam edin.
  4. Addım 3-də təsvir olunan keçid funksiyası istifadə olunur walkTrie (), bu funksiya üçlüyü keçir və ən uzun ümumi prefiks yolunu axtarır və müvafiq ən uzun ümumi prefiksi qaytarır.
  5. Sonda bir sürücü funksiyasından istifadə edirik longestCommonPrefix () yuxarıda göstərilən bütün funksiyaları özündə birləşdirən və verilmiş simlər sırası arasında ən uzun yayılmış prefiksi qaytaran.

 

Trie istifadə edilən ən uzun ümumi prefiksPin

Trie istifadə edərək ən uzun yayılmış prefiks üçün C ++ proqramı

#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 istifadə edərək ən uzun yayılmış prefiks üçün Java proqramı

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

Mürəkkəblik təhlili

  1. Zamanın mürəkkəbliyi: T (n) = O (mn), alınan vaxtın yuxarı hüdudu qurmaq üçlük.
  2. Kosmik Mürəkkəblik: A (n) = O (mn), üçlü yaddaşda yerin yuxarı hüdudunu tutur.

harada

n = ən uzun sətrin uzunluğu

m = simli massivdəki simlərin sayı.

References

Crack Sistemi Dizayn Müsahibələri
Translate »