Trie를 사용하는 가장 긴 공통 접두사

난이도 하드
자주 묻는 질문 어도비 벽돌 아마존 Apple 블룸버그 게시물에서 이베이 Facebook 구글 Microsoft
나무 시도조회수 99

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

. 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 데이터 구조를 사용하고, 주어진 모든 문자열을 여기에 삽입하고, trie를 횡단하고, 분기없이 trie에서 가장 긴 경로를 찾는 것입니다. 그런 길을 따라 얻은 캐릭터는 우리가 필요합니다 가장 긴 공통 접두사.

Trie를 사용한 가장 긴 공통 접두사 알고리즘

  1. 트라이를 구성하고 모든 입력 문자열을 트라이에 삽입합니다. 끼워 넣다() 함수는 주어진 문자열 배열에서 개별 문자열을 삽입하는 데 사용됩니다. ConstructTrie () 모든 입력 문자열을 반복적으로 삽입하는 데 사용됩니다.
  2. 가장 긴 공통 접두사를 접두사 변하기 쉬운.
  3. 이제 트라이의 루트 노드에서 순회를 시작하고 다음을 수행합니다.
    1. 노드에 단일 자식이 있는지 확인하십시오. 자식이 없거나 둘 이상인 경우 순회를 종료합니다. 트라이 노드의 null이 아닌 자식의 수는 다음을 사용하여 계산됩니다. 기능 countChildren ().
    2. 노드에 단일 자식이있는 경우 해당 자식으로 이동하고 해당 노드에 해당하는 문자를 접두사에 추가합니다.
    3. 자식이없는 (또는 둘 이상의 자식) 노드가 발견 될 때까지 1 단계와 2 단계를 반복합니다. or 문자열 배열에서 가장 짧은 문자열의 마지막 문자를 저장하는 트라이 노드에 도달합니다. 순회의 각 단계 동안 순회 된 각 트라이 노드에 해당하는 문자를 계속 추가합니다.
  4. 3 단계에서 설명한 순회는 함수를 사용하여 구현됩니다. walkTrie (), 이 함수는 trie를 순회하고 가장 긴 공통 접두사 경로를 찾고 해당하는 가장 긴 공통 접두사를 반환합니다.
  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 = string 형 배열의 문자열 수.

참조

균열 시스템 설계 인터뷰
Translate »