การสร้างคำโดยใช้การต่อคำในพจนานุกรมสองคำใน C++

ในปัญหานี้ เราได้รับพจนานุกรมและคำศัพท์ งานของเราคือตรวจสอบว่าสามารถสร้าง wor ที่กำหนดโดยใช้การต่อคำในพจนานุกรมสองคำหรือไม่

ในขณะที่การสร้างคำที่กำหนด การทำซ้ำคำนั้นไม่ถูกกฎหมาย

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

อินพุต

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

ผลลัพธ์

yes

คำอธิบาย

tutorialspoint is created using tutorials and point.

เพื่อแก้ปัญหานี้ เราจะเก็บองค์ประกอบทั้งหมดของพจนานุกรมไว้ในทรีคำนำหน้าที่เรียกกันทั่วไปว่า Trie จากนั้นให้ค้นหาคำนำหน้าของคำในกลุ่ม Trie หากพบว่าแยกออกเป็นสองคำและค้นหาส่วนอื่นของคำ หากพบให้คืนค่าจริง มิฉะนั้น เท็จ

โปรแกรมแสดงการดำเนินการแก้ไข

ตัวอย่าง

#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