資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究使用 C++ 中兩個詞典單詞的連線形成單詞
在此問題中，提供了一個詞典和一個單詞。我們的任務是檢查是否可以使用兩個詞典單詞的連線來形成給定的單詞。
在形成給定的單詞時，單詞的重複是不合法的。
我們舉個例子來理解這個問題，
輸入
dictionary = {“hello”, “tutorials”, “program” , “problem”, “coding”, “point”} word = “tutorialspoint”輸出
yes
說明
tutorialspoint is created using tutorials and point.
要解決此問題，我們將在字首樹（通常稱為字典樹）中儲存詞典的所有元素。然後在字典樹中搜索單詞的字首，如果找到，將其分成兩部分並搜尋單詞的另一部分。如果找到，則返回 true，否則返回 false。
顯示解決方案實現的程式，
示例
#include<bits/stdc++.h>
using namespace std;
#define char_int(c) ((int)c - (int)'a')
#define SIZE (26)
struct TrieNode{
TrieNode *children[26];
bool isLeaf;
};
TrieNode *getNode(){
TrieNode * newNode = new TrieNode;
newNode->isLeaf = false;
for (int i =0 ; i< 26 ; i++)
newNode->children[i] = NULL;
return newNode;
}
void insert(TrieNode *root, string Key){
int n = Key.length();
TrieNode * pCrawl = root;
for (int i=0; i<n; i++){
int index = char_int(Key[i]);
if (pCrawl->children[index] == NULL)
pCrawl->children[index] = getNode();
pCrawl = pCrawl->children[index];
}
pCrawl->isLeaf = true;
}
int prefixSearch(struct TrieNode *root, string key){
int pos = -1, level;
struct TrieNode *pCrawl = root;
for (level = 0; level < key.length(); level++){
int index = char_int(key[level]);
if (pCrawl->isLeaf == true)
pos = level;
if (!pCrawl->children[index])
return pos;
pCrawl = pCrawl->children[index];
}
if (pCrawl != NULL && pCrawl->isLeaf)
return level;
}
bool isWordCreated(struct TrieNode* root, string word){
int len = prefixSearch(root, word);
if (len == -1)
return false;
string split_word(word, len, word.length()-(len));
int split_len = prefixSearch(root, split_word);
return (len + split_len == word.length());
}
int main() {
vector<string> dictionary = {"tutorials", "program", "solving", "point"};
string word = "tutorialspoint";
TrieNode *root = getNode();
for (int i=0; i<dictionary.size(); i++)
insert(root, dictionary[i]);
cout<<"Word formation using dictionary is ";
isWordCreated(root, word)?cout<<"possible" : cout<<"not possible";
return 0;
}輸出
Word formation using dictionary is possible
更新時間： 2020 年 7 月 17 日
158 次瀏覽
廣告