資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究在 C++ 中查詢給定列表中每個單詞的最短唯一字首
在此問題中，我們給定一個單詞陣列 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
更新於：16-3-2021
161 次瀏覽
廣告