मान लीजिए हमारे पास एक पैटर्न और str नामक एक स्ट्रिंग है, हमें जांचना होगा कि क्या str उसी पैटर्न का अनुसरण करता है या नहीं। यहां पैटर्न का अनुसरण करने का अर्थ है पूर्ण मिलान, जैसे कि पैटर्न में एक अक्षर और str में एक गैर-खाली सबस्ट्रिंग के बीच एक बायजेक्शन हो।
तो, यदि इनपुट पैटर्न "abaa" है, str "orangegreenorangeorange" है, तो आउटपुट true होगा
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −
solve() नामक एक फ़ंक्शन परिभाषित करें, जो i, j, ptr, s, एक मैप m, used नामक एक सेट लेगा,
यदि i >= s का आकार और j >= ptr का आकार, तो −
true लौटाएं
यदि i >= s का आकार या j >= ptr का आकार, तो −
false लौटाएं
यदि ptr[j], m में है, तो −
req := m[ptr[j]]
len := req का आकार
यदि len, s के आकार से अधिक है, तो −
false लौटाएं
यदि इंडेक्स (i से len-1) से s का सबस्ट्रिंग req के समान है और solve(i + len, j + 1, ptr, s, m, used), तो −
true लौटाएं
false लौटाएं
अन्यथा
x := ptr[j]
k := i से आरंभ करें, जब k, s के आकार से कम, अद्यतन करें (k को 1 से बढ़ाएं), करें −
temp := इंडेक्स (i से k - i) से s का सबस्ट्रिंग
यदि temp, used में है, तो −
निम्नलिखित भाग को अनदेखा करें, अगले पुनरावृत्ति पर जाएं
m[x] := temp
temp को used में डालें
यदि solve(k + 1, j + 1, ptr, s, m, used), तो −
true लौटाएं
m से x हटाएं
used से temp हटाएं
false लौटाएं
मुख्य विधि से निम्नलिखित करें −
एक मैप m परिभाषित करें
एक सेट used परिभाषित करें
solve(0, 0, ptr, s, m, used) लौटाएं
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें −
#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