Tạo từ bằng cách ghép hai từ từ điển trong C ++

Trong bài toán này, chúng ta được cung cấp một từ điển và một từ. Nhiệm vụ của chúng tôi là kiểm tra xem có thể hình thành từ xấu nhất định bằng cách ghép hai từ trong từ điển hay không.

Trong khi hình thành các từ đã cho, việc lặp lại các từ là không hợp pháp.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào

dictionary = {“hello”, “tutorials”, “program” , “problem”, “coding”, “point”} word = “tutorialspoint”

Đầu ra

yes

Giải thích

tutorialspoint is created using tutorials and point.

Để giải quyết vấn đề này, chúng tôi sẽ lưu trữ tất cả các phần tử của từ điển trong một cây tiền tố thường được gọi là trie. Và sau đó tìm kiếm tiền tố của từ trong bộ ba, nếu tìm thấy hãy chia nó thành hai và tìm kiếm phần khác của từ. Nếu nó được tìm thấy, trả về true, ngược lại là false.

Chương trình hiển thị việc thực hiện 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<<"Word formation using dictionary is ";
   isWordCreated(root, word)?cout<<"possible" : cout<<"not possible";
   return 0;
}

Đầu ra

Word formation using dictionary is possible