Word Pattern II ใน C++

สมมติว่าเรามีรูปแบบ (pattern) และสตริง str เราต้องตรวจสอบว่า str ปฏิบัติตามรูปแบบเดียวกันหรือไม่ โดย pattern follow หมายถึงการจับคู่แบบเต็ม (full match) ที่มี bijection ระหว่างตัวอักษรใน pattern กับสตริงย่อยที่ไม่ว่างใน str

เช่น ถ้าอินพุตคือ pattern = "abaa", str = "orangegreenorangeorange" ผลลัพธ์จะเป็น true

ในการแก้ปัญหานี้ เราจะใช้ Backtracking + Hash Map/Set ทำตามขั้นตอน:

• ฟังก์ชัน solve(i,j,ptr,s,m,used): i,j ดัชนีใน s และ ptr; ถ้าครบทั้งคู่ return true; ถ้าหนึ่งอย่างหมด return false
• ถ้า ptr[j] อยู่ใน map m: req = m[ptr[j]]; ตรวจสอบ s.substr(i,len)==req และ solve(i+len,j+1,...)
• มิฉะนั้น: ลองทุกสตริงย่อย temp = s.substr(i, k-i+1) สำหรับ k=i..s.size()-1; ถ้า temp ไม่อยู่ใน used: m[ptr[j]]=temp; used.insert(temp); ถ้า solve(k+1,j+1,...) true คืน true; ย้อนกลับ (erase)
• คืนค่า false

ตัวอย่าง

ลองดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น:

#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 m; set used;
        return solve(0,0,ptr,s,m,used);
    }
};
main(){
    Solution ob;
    cout << (ob.wordPatternMatch("abaa", "orangegreenorangeorange"));
}

อินพุต

"abaa", "orangegreenorangeorange"

เอาต์พุต

1