सी++ में वर्ड पैटर्न II

मान लीजिए कि हमारे पास एक पैटर्न और एक स्ट्रिंग है जिसे str कहा जाता है, हमें यह जांचना होगा कि str उसी पैटर्न का अनुसरण करता है या नहीं। यहां पैटर्न फॉलो का अर्थ है एक पूर्ण मिलान, जैसे कि पैटर्न में एक अक्षर और str में एक गैर-रिक्त सबस्ट्रिंग के बीच एक आक्षेप है।

इसलिए, यदि इनपुट पैटर्न की तरह है "abaa", str "ऑरेंजग्रीनोरेंजोरेंज" है, तो आउटपुट सही होगा

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक फ़ंक्शन हल करें () को परिभाषित करें, यह i, j, ptr, s, एक मैप m, एक सेट जिसे यूज्ड कहा जाता है,

  लेगा

• यदि i>=s का आकार और j>=ptr का आकार, तो −

  • सही लौटें

• यदि i>=s का आकार या j>=ptr का आकार, तो −

  • झूठी वापसी

• अगर ptr[j] m में है, तो -

  • अनुरोध :=एम[ptr[j]]

  • लेन:=अनुरोध का आकार

  • यदि लेन> s का आकार है, तो −

    • झूठी वापसी

  • यदि अनुक्रमणिका (i से len-1) में s का प्रतिस्थापन req और हल (i + len, j + 1, ptr, s, m, प्रयुक्त) के समान है, तो -

    • सही लौटें

  • झूठी वापसी

• अन्यथा

  • एक्स:=पीटीआर [जे]

  • प्रारंभ करने के लिए k :=i, जब k

    • अस्थायी:=सूचकांक से s का विकल्प (i से k - i)

    • यदि अस्थायी का उपयोग किया जाता है, तो -

      • निम्नलिखित भाग पर ध्यान न दें, अगले पुनरावृत्ति पर जाएं

    • एम [एक्स]:=अस्थायी

    • उपयोग में अस्थायी डालें

    • यदि हल करें (k + 1, j + 1, ptr, s, m, प्रयुक्त), तो -

      • सही लौटें

    • m से x हटाएं

    • उपयोग किए गए से अस्थायी हटाएं

• झूठी वापसी

• मुख्य विधि से निम्न कार्य करें -

• एक नक्शा परिभाषित करें मी

• इस्तेमाल किए गए एक सेट को परिभाषित करें

• वापसी हल (0, 0, पीटीआर, एस, एम, प्रयुक्त)

#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