ట్రీని ఉపయోగించి పొడవైన సాధారణ ఉపసర్గ


కఠినత స్థాయి హార్డ్
తరచుగా అడుగుతుంది Adobe అమెజాన్ ఆపిల్ బ్లూమ్బెర్గ్ eBay <span style="font-family: Mandali; ">ఫేస్‌బుక్ </span> గూగుల్ మైక్రోసాఫ్ట్
స్ట్రింగ్ ట్రీ ట్రీ

లో ట్రీని ఉపయోగించి పొడవైన సాధారణ ఉపసర్గ మేము సమితి ఇచ్చిన సమస్య తీగలను, పొడవైన సాధారణ ఉపసర్గను కనుగొనండి. అంటే అన్ని తీగలకు సాధారణమైన ఉపసర్గ భాగాన్ని కనుగొనండి.

ఉదాహరణ

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

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

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

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

ట్రీని ఉపయోగించి పొడవైన సాధారణ ఉపసర్గ కోసం అప్రోచ్

ట్రీ డేటా స్ట్రక్చర్‌ను ఉపయోగించడం, ఇచ్చిన అన్ని తీగలను దానిలోకి చొప్పించడం, ట్రీని దాటడం మరియు ట్రీలో పొడవైన మార్గం కోసం శాఖలు లేకుండా చూడటం దీని ఆలోచన. అటువంటి మార్గంలో పొందిన అక్షరాలు మనకు అవసరం పొడవైన సాధారణ ఉపసర్గ.

ట్రీని ఉపయోగించి పొడవైన సాధారణ ఉపసర్గ కోసం అల్గోరిథం

  1. ఒక ట్రీని నిర్మించి, అన్ని ఇన్పుట్ తీగలను ట్రీలోకి చొప్పించండి. చొప్పించు () ఇచ్చిన తీగల శ్రేణి నుండి వ్యక్తిగత స్ట్రింగ్‌ను చొప్పించడానికి ఫంక్షన్ ఉపయోగించబడుతుంది కన్స్ట్రక్ ట్రీ () అన్ని ఇన్పుట్ తీగలను పునరావృతంగా చొప్పించడానికి ఉపయోగిస్తారు.
  2. లో పొడవైన సాధారణ ఉపసర్గను నిల్వ చేయండి ఉపసర్గ వేరియబుల్.
  3. ఇప్పుడు, ట్రీ యొక్క రూట్ నోడ్ నుండి ట్రావెర్సల్ ప్రారంభించండి మరియు ఈ క్రింది వాటిని చేయండి:
    1. నోడ్‌కు ఒకే సంతానం ఉందో లేదో తనిఖీ చేయండి. దీనికి పిల్లలు లేదా ఒకటి కంటే ఎక్కువ పిల్లలు లేరు, ట్రావెర్సల్‌ను ముగించారు. ట్రీ నోడ్ యొక్క శూన్య పిల్లల సంఖ్యను లెక్కించడం ఉపయోగించి జరుగుతుంది ఫంక్షన్ countChildren ().
    2. నోడ్‌కు ఒకే బిడ్డ ఉంటే, ఆ బిడ్డకు వెళ్లి, ఆ నోడ్‌కు అనుగుణమైన అక్షరాన్ని ఉపసర్గలో చేర్చండి.
    3. పిల్లలు లేని నోడ్ (లేదా ఒకటి కంటే ఎక్కువ పిల్లలు) కనుగొనబడే వరకు 1 మరియు 2 దశలను పునరావృతం చేయండి or మేము తీగ శ్రేణిలో చిన్నదైన స్ట్రింగ్ యొక్క చివరి అక్షరాన్ని నిల్వ చేసే ట్రీ నోడ్‌కు చేరుకుంటాము. ట్రావెర్సల్ యొక్క ప్రతి దశలో, ప్రయాణించిన ప్రతి ట్రీ నోడ్‌కు అనుగుణమైన అక్షరాన్ని జోడించడం కొనసాగించండి.
  4. దశ 3 లో వివరించిన ట్రావెర్సల్ ఫంక్షన్ ఉపయోగించి అమలు చేయబడుతుంది వాక్‌ట్రీ (), ఈ ఫంక్షన్ ట్రీని దాటుతుంది మరియు పొడవైన సాధారణ ఉపసర్గ మార్గం కోసం చూస్తుంది మరియు సంబంధిత పొడవైన సాధారణ ఉపసర్గను అందిస్తుంది.
  5. చివరికి, మేము డ్రైవర్ ఫంక్షన్‌ను ఉపయోగిస్తాము longestCommonPrefix () ఇది పైన పేర్కొన్న అన్ని ఫంక్షన్లను మిళితం చేస్తుంది మరియు ఇచ్చిన తీగల శ్రేణిలో పొడవైన సాధారణ ఉపసర్గను అందిస్తుంది.

 

ట్రీని ఉపయోగించి పొడవైన సాధారణ ఉపసర్గ

ట్రీని ఉపయోగించి పొడవైన సాధారణ ఉపసర్గ కోసం సి ++ ప్రోగ్రామ్

#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

ట్రీని ఉపయోగించి పొడవైన సాధారణ ఉపసర్గ కోసం జావా ప్రోగ్రామ్

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 = స్ట్రింగ్ శ్రేణిలోని తీగల సంఖ్య.

ప్రస్తావనలు