ধরি আমাদের একটি প্যাটার্ন (pattern) এবং একটি স্ট্রিং str আছে। আমাদের যাচাই করতে হবে কি str প্যাটার্নটি অনুসরণ করে কিনা। এখানে প্যাটার্ন অনুসরণ বলতে পূর্ণ মিল (full match) বোঝায়, অর্থাৎ প্যাটার্নের প্রতিটি অক্ষর এবং str-এর নন-এম্পটি সাবস্ট্রিংর মধ্যে একটি বাইজেকশন (bijection) থাকবে।
উদাহরণস্বরূপ, pattern = "abaa", str = "orangegreenorangeorange" হলে আউটপুট হবে true।
সমাধানের ধাপসমূহ
solve(i, j, ptr, s, m, used)ফাংশন:- যদি i >= s.size() এবং j >= ptr.size(): true ফেরত
- যদি i >= s.size() বা j >= ptr.size(): false ফেরত
- যদি ptr[j] m-তে থাকে:
- req := m[ptr[j]], len := req.size()
- যদি len > s.size() - i: false ফেরত
- যদি s.substr(i, len) == req এবং solve(i+len, j+1, ptr, s, m, used): true ফেরত
- false ফেরত
- অন্যথায়:
- x := ptr[j]
- k = i থেকে s.size()-1 পর্যন্ত:
- temp := s.substr(i, k-i+1)
- যদি temp used-তে থাকে: continue
- m[x] = temp; used.insert(temp)
- যদি solve(k+1, j+1, ptr, s, m, used): true ফেরত
- m.erase(x); used.erase(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& m, set& 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 m;
set used;
return solve(0, 0, ptr, s, m, used);
}
};
int main() {
Solution ob;
cout << (ob.wordPatternMatch("abaa", "orangegreenorangeorange"));
}
ইনপুট
"abaa", "orangegreenorangeorange"
আউটপুট
1
