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

ในโจทย์นี้ เราได้รับพจนานุกรม (dictionary) และคำหนึ่งคำ งานของเราคือตรวจสอบว่าคำที่ให้มาสามารถสร้างได้จากการต่อสตริง (concatenation) ของสองคำจากพจนานุกรมหรือไม่

ขณะสร้างคำที่ให้มา การซ้ำของคำไม่ได้รับอนุญาต

ตัวอย่าง

อินพุต

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

เอาต์พุต

yes

คำอธิบาย

tutorialspoint ถูกสร้างจาก tutorials และ point

เพื่อแก้ปัญหานี้ เราจะเก็บองค์ประกอบทั้งหมดของพจนานุกรมใน prefix tree ซึ่งรู้จักกันในชื่อ Trie จากนั้นค้นหา prefix ของคำใน trie หากพบ ให้แบ่งเป็นสองส่วน และค้นหาส่วนที่สองของคำ หากพบ คืนค่า 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 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