ในปัญหานี้ เราได้รับอาร์เรย์ของคำ arr[] งานของเราคือค้นหาคำนำหน้าเฉพาะที่สั้นที่สุดสำหรับทุกคำในรายการที่กำหนด
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
arr[] = {“learn”, “programming”, “code”} ผลลัพธ์
c leap lear p
แนวทางการแก้ปัญหา
วิธีแก้ปัญหาง่ายๆ ก็คือการค้นหาคำนำหน้าทั้งหมดของคำนั้น จากนั้นให้ตรวจสอบว่าคำนั้นเป็นคำนำหน้าของคำอื่นๆ ในอาร์เรย์หรือไม่ ถ้าไม่ใช่ ให้พิมพ์
แนวทางที่มีประสิทธิภาพ คือการใช้โครงสร้างข้อมูลแบบทดลอง เราจะสร้างการทดลองและเก็บคำศัพท์ทั้งหมด จากนั้นให้ค้นหาความถี่ของการเยี่ยมชมแต่ละคำในขณะที่ใส่คำ เราจะพบเส้นทางไปยังรูทซึ่งเป็นคำนำหน้า เราจะพิมพ์คำนำหน้าทั้งหมดโดยเริ่มจากโหนดที่มีความถี่ 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
