C++ এ ওয়ার্ড প্যাটার্ন II

ধরুন আমাদের str নামক একটি প্যাটার্ন এবং একটি স্ট্রিং আছে, আমাদের পরীক্ষা করতে হবে str একই প্যাটার্ন অনুসরণ করছে কি না। এখানে প্যাটার্ন ফলো মানে সম্পূর্ণ মিল, যেমন প্যাটার্নে একটি অক্ষর এবং স্ট্র-এ একটি অ-খালি সাবস্ট্রিং-এর মধ্যে একটি দ্বিখণ্ডন রয়েছে।

সুতরাং, যদি ইনপুটটি প্যাটার্নের মত হয় "abaa", str হয় "orangegreenorangeorange", তাহলে আউটপুট সত্য হবে

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি ফাংশন সল্ভ() সংজ্ঞায়িত করুন, এটি i, j, ptr, s, একটি মানচিত্র m, একটি সেটকে ব্যবহৃত বলে,

• যদি i>=s এর সাইজ এবং j>=ptr এর সাইজ হয়, তাহলে −

  • প্রত্যাবর্তন সত্য

• যদি i>=s এর সাইজ বা j>=ptr এর সাইজ হয়, তাহলে −

  • ফেরত মিথ্যা

• যদি ptr[j] m হয়, তাহলে −

  • req :=m[ptr[j]]

  • len :=অনুরোধের আকার

  • যদি len> s এর আকার হয়, তাহলে −

    • ফেরত মিথ্যা

  • যদি সূচী থেকে s-এর সাবস্ট্রিং (i থেকে len-1) হয় req এবং সমাধান (i + len, j + 1, ptr, s, m, ব্যবহৃত), তাহলে −

    • প্রত্যাবর্তন সত্য

  • ফেরত মিথ্যা

• অন্যথায়

  • x :=ptr[j]

  • আরম্ভ করার জন্য k :=i, যখন k

    • temp :=সূচক থেকে s এর সাবস্ট্রিং (i থেকে k - i)

    • যদি temp ব্যবহার করা হয়, তাহলে -

      • নিম্নলিখিত অংশ উপেক্ষা করুন, পরবর্তী পুনরাবৃত্তি এড়িয়ে যান

    • m[x] :=temp

    • ব্যবহৃত মধ্যে temp সন্নিবেশ করান

    • যদি সমাধান (k + 1, j + 1, ptr, s, m, ব্যবহৃত হয়), তাহলে −

      • প্রত্যাবর্তন সত্য

    • m

      থেকে x মুছে দিন

    • ব্যবহৃত থেকে তাপমাত্রা মুছুন

• ফেরত মিথ্যা

• প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -

• একটি মানচিত্র m

  সংজ্ঞায়িত করুন

• ব্যবহৃত একটি সেট সংজ্ঞায়িত করুন

• রিটার্ন সমাধান (0, 0, ptr, s, m, ব্যবহৃত)

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   bool solve(int i, int j, string ptr, string s, map <char, string>& m, set<string>& used){
      if (i >= s.size() && j >= ptr.size()) {
         return true;
      }
      if (i >= s.size() || j >= ptr.size())
         return false;
      if (m.count(ptr[j])) {
         string req = m[ptr[j]];
         int len = req.size();
         if (len > s.size() - i)
            return false;
         if ((s.substr(i, len) == req) && solve(i + len, j + 1, ptr, s, m, used))
            return true;
         return false;
      }
      else {
         char x = ptr[j];
         for (int k = i; k < s.size(); k++) {
            string temp = s.substr(i, k - i + 1);
            ;
            if (used.count(temp))
               continue;
            m[x] = temp;
            used.insert(temp);
            if (solve(k + 1, j + 1, ptr, s, m, used))
               return true;
            m.erase(x);
            used.erase(temp);
         }
      }
      return false;
   }
   bool wordPatternMatch(string ptr, string s) {
      map<char, string> m;
      set<string> used;
      return solve(0, 0, ptr, s, m, used);
   }
};
main(){
   Solution ob;
   cout << (ob.wordPatternMatch("abaa", "orangegreenorangeorange"));
}

"abaa" "orangegreenorangeorange"

1