Giả sử chúng ta có một mẫu và một chuỗi gọi là str, chúng ta phải kiểm tra xem str có tuân theo cùng một mẫu hay không. Ở đây, theo sau mẫu có nghĩa là một đối sánh đầy đủ, sao cho có sự phân biệt giữa một ký tự trong mẫu và một chuỗi con không trống trong str.
Vì vậy, nếu đầu vào giống như mẫu là "abaa", str là "orangegreenorangeorange", thì đầu ra sẽ là true
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Xác định một hàm giải quyết (), điều này sẽ lấy i, j, ptr, s, một ánh xạ m, một tập hợp được gọi là đã sử dụng,
-
nếu i> =kích thước của s và j> =kích thước của ptr, thì -
-
trả về true
-
-
nếu i> =kích thước của s hoặc j> =kích thước của ptr, thì -
-
trả về false
-
-
nếu ptr [j] tính bằng m thì -
-
yêu cầu:=m [ptr [j]]
-
len:=size of req
-
if len> size of s, then -
-
trả về false
-
-
nếu chuỗi con của s từ chỉ mục (i đến len-1) giống với req và giải quyết (i + len, j + 1, ptr, s, m, used), thì -
-
trả về true
-
-
trả về false
-
-
Nếu không
-
x:=ptr [j]
-
để khởi tạo k:=i, khi k
-
temp:=chuỗi con của s từ chỉ mục (i đến k - i)
-
nếu tạm thời được sử dụng, thì -
-
Bỏ qua phần sau, chuyển sang phần tiếp theo
-
-
m [x]:=temp
-
chèn tạm thời vào sử dụng
-
nếu giải quyết (k + 1, j + 1, ptr, s, m, đã sử dụng), thì -
-
trả về true
-
-
xóa x khỏi m
-
xóa tạm thời khỏi đã sử dụng
-
-
-
trả về false
-
Từ phương thức chính, hãy làm như sau -
-
Xác định một bản đồ m
-
Xác định một tập hợp được sử dụng
-
trả về giải quyết (0, 0, ptr, s, m, đã qua sử dụng)
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#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"));
} Đầu vào
"abaa" "orangegreenorangeorange"
Đầu ra
1