Tìm tiền tố duy nhất ngắn nhất cho mỗi từ trong danh sách trong C++

Trong bài toán này, cho mảng các từ arr[]. Nhiệm vụ là tìm tiền tố duy nhất ngắn nhất cho mỗi từ trong danh sách.

Ví dụ minh họa:

Đầu vào

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

Đầu ra

c leap lear p

Phương pháp giải

Cách đơn giản: tìm tất cả tiền tố của từ, kiểm tra xem có phải tiền tố của từ khác không. Cách hiệu quả: dùng Trie. Xây Trie chứa tất cả từ, lưu tần suất truy cập. Dùng từ tìm đường đến gốc là tiền tố. In tiền tố từ nút có tần suất 1.

Chương trình minh họa:

Ví dụ

#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; 
}

Kết quả

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