C++-এ কনক্যাটেনেটেড শব্দ খুঁজে বের করা

কনক্যাটেনেটেড শব্দ সমস্যা

একটি শব্দের তালিকা দেওয়া আছে। আমাদের কাজ হল সেই তালিকায় থাকা সব কনক্যাটেনেটেড শব্দ খুঁজে বের করা। একটি কনক্যাটেনেটেড শব্দ হল এমন একটি স্ট্রিং যা তালিকার অন্তত দুটি ছোট শব্দের মিলনে গঠিত।

উদাহরণস্বরূপ, শব্দগুলো হলো: ["cow", "cows", "cowsgoatcows", "goat", "goatcowsgoat", "hippopotamuses", "deer", "deercowgoatcow"]। ফলাফল হবে: ["cowsgoatcows", "goatcowsgoat", "deercowgoatcow"]

সমাধানের পদ্ধতি (ট্রাই + ডিপি)

এই সমস্যাটি সমাধানের জন্য আমরা ট্রাই (Trie) এবং ডাইনামিক প্রোগ্রামিং (DP) ব্যবহার করব।

• Trie Node: প্রতিটি নোডে একটি ম‍্যাপ child এবং একটি বুলিয়ান isEnd থাকে
• isPresent(str, head, idx, dp) ফাংশন:
  • যদি idx >= str.size(), true ফেরত দিন
  • যদি dp[idx] != -1, মেমোইজড মান ফেরত দিন
  • ট্রাই-তে ট্রাভার্স করুন, যদি কোনো শব্দের শেষ পাওয়া যায়, তবে রিকার্সিভলি বাকি অংশ চেক করুন
  • dp[idx] = ok সেট করে ফেরত দিন
• insertNode(head, s) ফাংশন: স্ট্রিং s ট্রাই-তে যোগ করুন
• মূল ফাংশন:
  • শব্দগুলো দৈর্ঘ্য অনুযায়ী সর্ট করুন
  • প্রতিটি শব্দের জন্য isPresent কল করুন
  • যদি true ফেরত দেয়, তবে এটি কনক্যাটেনেটেড শব্দ, ফলাফলে যোগ করুন
  • অন্যথায় ট্রাই-তে ইনসার্ট করুন

C++ কোড উদাহরণ

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<string> v) {
    cout << "[";
    for(int i = 0; i < v.size(); i++) {
        cout << v[i] << ", ";
    }
    cout << "]" << endl;
}

struct Node {
    bool isEnd;
    map<char, Node*> child;
    Node() { isEnd = false; }
};

class Solution {
public:
    bool isPresent(string str, Node* head, int idx, vector<int>& dp) {
        if(idx >= str.size()) return true;
        if(dp[idx] != -1) return dp[idx];
        Node* curr = head;
        bool ok = false;
        for(int i = idx; i < str.size(); i++) {
            char x = str[i];
            if(!curr->child[x]) break;
            curr = curr->child[x];
            if(curr->isEnd) {
                ok |= isPresent(str, head, i + 1, dp);
            }
        }
        return dp[idx] = ok;
    }
    
    static bool cmp(string s1, string s2) {
        return s1.size() < s2.size();
    }
    
    void insertNode(Node* head, string s) {
        Node* curr = head;
        for(int i = 0; i < s.size(); i++) {
            char x = s[i];
            if(!curr->child[x]) {
                curr->child[x] = new Node();
            }
            curr = curr->child[x];
        }
        curr->isEnd = true;
    }
    
    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
        Node* head = new Node();
        sort(words.begin(), words.end(), cmp);
        vector<string> ret;
        for(int i = 0; i < words.size(); i++) {
            string curr = words[i];
            if(curr == "") continue;
            vector<int> dp(curr.size(), -1);
            if(isPresent(curr, head, 0, dp)) {
                ret.push_back(curr);
            } else {
                insertNode(head, curr);
            }
        }
        return ret;
    }
};

int main() {
    Solution ob;
    vector<string> v = {"cow","cows","cowsgoatcows","goat","goatcowsgoat","hippopotamuses","deer","deercowgoatcow"};
    print_vector(ob.findAllConcatenatedWordsInADict(v));
    return 0;
}

ইনপুট

{"cow","cows","cowsgoatcows","goat","goatcowsgoat","hippopotamuses","deer","deercowgoatcow"}

আউটপুট

[cowsgoatcows, goatcowsgoat, deercowgoatcow, ]