สมมติว่าเรามีรูปแบบและสตริงที่เรียกว่า str เราต้องตรวจสอบว่า str มีรูปแบบเดียวกันหรือไม่ รูปแบบตามนี้หมายถึงการจับคู่แบบเต็มรูปแบบ โดยที่จะมีการ bijection ระหว่างตัวอักษรในรูปแบบและสตริงย่อยที่ไม่ว่างเปล่าใน str
ดังนั้น หากอินพุตเหมือนกับรูปแบบคือ "abaa" str คือ "orangegreenorangeorange" ผลลัพธ์จะเป็นจริง
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดฟังก์ชัน Solve() ซึ่งจะใช้ i, j, ptr, s, map m ชุดหนึ่งเรียกว่าใช้แล้ว
-
ถ้า i>=ขนาดของ s และ j>=ขนาดของ ptr แล้ว −
-
คืนความจริง
-
-
ถ้า i>=ขนาดของ s หรือ j>=ขนาดของ ptr แล้ว −
-
คืนค่าเท็จ
-
-
ถ้า ptr[j] อยู่ในหน่วย m แล้ว −
-
ต้องการ :=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)
-
หากมีการใช้อุณหภูมิ −
-
ละเว้นส่วนต่อไปนี้ ข้ามไปยังการทำซ้ำถัดไป
-
-
m[x] :=อุณหภูมิ
-
ใส่อุณหภูมิในการใช้งาน
-
ถ้าแก้ (k + 1, j + 1, ptr, s, m, ใช้แล้ว) −
-
คืนความจริง
-
-
ลบ x จาก m
-
ลบอุณหภูมิที่ใช้
-
-
-
คืนค่าเท็จ
-
จากวิธีหลัก ให้ทำดังต่อไปนี้ −
-
กำหนดหนึ่งแผนที่ 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
