Mẫu từ II trong C++

Cho pattern và chuỗi str, kiểm tra str có tuân theo pattern không. Pattern follow nghĩa là ánh xạ 1-1 giữa ký tự trong pattern và chuỗi con không rỗng trong str.

Ví dụ: pattern = "abaa", str = "orangegreenorangeorange" → true

Phương pháp giải

Backtracking với ánh xạ char→string và set đã dùng. Hàm solve(i, j): i vị trí trong str, j vị trí trong pattern. Nếu pattern[j] đã có ánh xạ, kiểm tra khớp. Nếu chưa, thử mọi chuỗi con bắt đầu từ i, thêm vào map/set, đệ quy, sau đó backtrack.

Ví dụ chương trình

#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");
    return 0;
}

Đầu vào

"abaa", "orangegreenorangeorange"

Đầu ra

1