โปรแกรมตรวจสอบว่าคำสอดคล้องกับรูปแบบ (Pattern) ใน C++

ให้ pattern p และสตริง str ต้องการตรวจสอบว่า str ตาม pattern p หรือไม่ โดยมี bijection ระหว่างตัวอักษรใน pattern กับคำใน str

ตัวอย่าง: pattern="cbbc", str="word pattern pattern word" → True c→word, b→pattern

ขั้นตอนการแก้ปัญหา

1. แยก str เป็นคำๆ ใส่ vector words
2. สร้าง encoding pattern: ให้ตัวอักษรใหม่แต่ละตัวได้หมายเลข 1,2,3... ต่อกันเป็นสตริง pat
3. ทำเหมือนกันกับ words ได้ pat1
4. ถ้า pat == pat1 → True

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool wordPattern(string pattern, string str) {
        istringstream iss(str);
        vector<string> words;
        string word;
        while (iss >> word) words.push_back(word);
        if (pattern.size() != words.size()) return false;
        
        unordered_map<char,int> p2i;
        unordered_map<string,int> w2i;
        string pat, pat1;
        int cnt = 0;
        
        for (char c : pattern) {
            if (!p2i.count(c)) p2i[c] = ++cnt;
            pat += to_string(p2i[c]);
        }
        cnt = 0;
        for (auto& w : words) {
            if (!w2i.count(w)) w2i[w] = ++cnt;
            pat1 += to_string(w2i[w]);
        }
        return pat == pat1;
    }
};

int main() {
    Solution ob;
    cout << ob.wordPattern("cbbc", "word pattern pattern word"); // 1
    return 0;
}

อินพุต

"cbbc", "word pattern pattern word"

เอาต์พุต

1