หาคำนำหน้าเฉพาะที่สั้นที่สุดสำหรับทุกคำในรายการที่กำหนดใน C++

ในปัญหานี้ เราได้รับอาร์เรย์ของคำ arr[] งานของเราคือหาคำนำหน้า (prefix) ที่สั้นที่สุดและเฉพาะตัวสำหรับทุกคำในรายการที่กำหนด

มาดูตัวอย่างเพื่อเข้าใจปัญหา

Input

arr[] = {"learn", "programming", "code"}

Output

c leap lear p

วิธีแก้ปัญหา

วิธีแก้ที่ง่ายคือหาคำนำหน้าทั้งหมดของคำ แล้วตรวจสอบว่ามันเป็นคำนำหน้าของคำอื่นในอาร์เรย์หรือไม่ ถ้าไม่ใช่ ให้พิมพ์มัน

วิธีที่มีประสิทธิภาพ คือใช้โครงสร้างข้อมูล trie เราจะสร้าง trie และเก็บคำทั้งหมด แล้วหาความถี่ของการเข้าชมสำหรับแต่ละคำขณะแทรก โดยใช้คำ เราจะหาเส้นทางไปยังรากซึ่งเป็นคำนำหน้า เราจะพิมพ์คำนำหน้าทั้งหมดตั้งแต่โหนดที่มีความถี่ 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