Chương trình kiểm tra từ có tuân theo mẫu cho trước trong C++

Mô tả bài toán

Cho mẫu pattern (xâu ký tự) và xâu str (các từ cách nhau bởi dấu cách). Kiểm tra xem str có tuân theo pattern không, tức là tồn tại ánh xạ một-một giữa ký tự trong pattern và từ trong str.

Ví dụ: pattern = "cbbc", str = "word pattern pattern word" → True.

Giải thuật

1. Tách str thành vector words.
2. Gán số thứ tự cho mỗi ký tự pattern lần đầu xuất hiện → tạo xâu pat.
3. Gán số thứ tự cho mỗi từ trong words lần đầu xuất hiện → tạo xâu pat1.
4. So sánh pat và pat1.

Ví dụ minh họa (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);
        unordered_map<char,int> p2i;
        int idx = 0;
        string pat;
        for (char c : pattern) {
            if (!p2i.count(c)) p2i[c] = ++idx;
            pat += to_string(p2i[c]);
        }
        unordered_map<string,int> w2i;
        idx = 0;
        string pat1;
        for (string& w : words) {
            if (!w2i.count(w)) w2i[w] = ++idx;
            pat1 += to_string(w2i[w]);
        }
        return pat == pat1;
    }
};

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

Đầu vào

"cbbc", "word pattern pattern word"

Đầu ra

1