C++에서 주어진 목록의 모든 단어에 대해 가장 짧은 고유 접두사 찾기

이 문제에서 우리는 단어의 배열 arr[]을 받습니다. 우리의 임무는 주어진 목록의 모든 단어에 대해 가장 짧은 고유 접두사를 찾는 것입니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력

arr[] = {“learn”, “programming”, “code”}

출력

c leap lear p

해결 방법

문제에 대한 간단한 해결책은 단어의 모든 접두사를 찾는 것입니다. 그런 다음 배열에 있는 다른 단어의 접두사인지 확인합니다. 그렇지 않은 경우 인쇄하십시오.

효율적인 접근 방식 tri 데이터 구조를 사용하는 것입니다. 우리는 트라이를 구성하고 모든 단어를 저장할 것입니다. 그런 다음 삽입하는 동안 각 단어에 대한 방문 빈도를 찾습니다. 단어를 사용하여 접두사인 루트에 대한 경로를 찾습니다. 빈도가 1인 노드에서 시작하는 모든 접두사를 인쇄합니다.

우리 솔루션의 작동을 설명하는 프로그램

예

#include<iostream>
using namespace std;
#define MAX 256
struct trieNode {
   struct trieNode *child[MAX];
   int freq;
};
struct trieNode *newTrieNode(void){
   struct trieNode *newNode = new trieNode;
   newNode->freq = 1;
   for (int i = 0; i<MAX; i++)
      newNode->child[i] = NULL;
   return newNode;
}
void insert(struct trieNode *root, string str) {
   int len = str.length();
   struct trieNode *pCrawl = root;
   for (int level = 0; level<len; level++) {
      int index = str[level];
      if (!pCrawl->child[index])
         pCrawl->child[index] = newTrieNode();
      else
         (pCrawl->child[index]->freq)++;
      pCrawl = pCrawl->child[index];
   }
}
void findShortestUniquePrefixRec(struct trieNode *root, char prefixChar[], int ind) {
   if (root == NULL)
      return;
   if (root->freq == 1) {
      prefixChar[ind] = '\0';
      cout<<prefixChar<<endl;
      return;
   }
   for (int i=0; i<MAX; i++) {
      if (root->child[i] != NULL) {
         prefixChar[ind] = i;
         findShortestUniquePrefixRec(root->child[i], prefixChar, ind+1);
      }
   }
}
void findShortestUniquePrefix(string arr[], int n) {
   struct trieNode *root = newTrieNode();
   root->freq = 0;
   for (int i = 0; i<n; i++)
      insert(root, arr[i]);
   char prefixChar[250];
   findShortestUniquePrefixRec(root, prefixChar, 0);
}
int main() {
   string arr[] = {"learn", "programming", "code", "leap"};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout<<"All Shortest unique prefix for every words in a given list are : \n";
   findShortestUniquePrefix(arr, n);
   return 0;
}

출력

All Shortest unique prefix for every words in a given list are −
c
leap
lear
p