Hình thành từ bằng nối hai từ điển trong C++

Trong bài toán này, chúng ta được cho một từ điển và một từ. Nhiệm vụ là kiểm tra xem từ cho trước có thể hình thành bằng cách nối hai từ trong từ điển.

Khi hình thành từ cho trước, lặp lại từ không được phép.

Hãy xem ví dụ để hiểu bài toán,

Đầu vào

từ điển = {“hello”, “tutorials”, “program” , “problem”, “coding”, “point”} từ = “tutorialspoint”

Đầu ra

yes

Giải thích

tutorialspoint được tạo bằng tutorials và point.

Để giải bài toán này, chúng ta sẽ lưu tất cả phần tử của từ điển trong một cây tiền tố thường gọi là trie. Sau đó tìm kiếm tiền tố của từ trong trie, nếu tìm thấy tách nó thành hai và tìm phần còn lại của từ. Nếu tìm thấy trả về true ngược lại false.

Chương trình triển khai giải pháp,

Ví dụ

#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<<"Hình thành từ bằng từ điển là ";    isWordCreated(root, word)?cout<<"có thể" : cout<<"không thể";    return 0; }

Đầu ra

Hình thành từ bằng từ điển là có thể