Word Pattern trong C++

Cho pattern (chuỗi ký tự) và str (chuỗi từ cách nhau bởi dấu cách). Kiểm tra str có tuân theo pattern không: ánh xạ 1-1 giữa ký tự pattern và từ trong str.

Ví dụ: pattern="cbbc", str="word pattern pattern word" → true (c↔word, b↔pattern).

Giải thuật

1. Tách str thành vector từ.
2. Nếu số từ ≠ độ dài pattern → false.
3. Dùng 2 unordered_map: char→index và string→index. Xây mã hóa pattern và từ, so sánh mã hóa.

Ví dụ triển khai C++

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

class Solution {
public:
    bool wordPattern(string pattern, string s) {
        istringstream iss(s);
        vector<string> words;
        string w;
        while (iss >> w) words.push_back(w);
        if (pattern.size() != words.size()) return false;
        
        unordered_map<char, int> p2i;
        unordered_map<string, int> w2i;
        for (int i = 0; i < pattern.size(); i++) {
            if (p2i[pattern[i]] != w2i[words[i]]) return false;
            p2i[pattern[i]] = w2i[words[i]] = i + 1;
        }
        return true;
    }
};

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

Đầu vào / Đầu ra

Input: "cbbc", "word pattern pattern word"
Output: true (1)