Word Pattern ใน C++

แนวคิด

สมมติว่ามี pattern และสตริง str ให้หาว่า str ตาม pattern เดียวกันหรือไม่ follow หมายถึงมี bijection ระหว่างตัวอักษรใน pattern และคำที่ไม่ว่างใน str

เช่น ถ้าอินพุตคือ pattern = "cbbc", str = "word pattern pattern word" ผลลัพธ์คือ True

วิธีแก้:

• strcin := str
• กำหนดอาร์เรย์คำ
• สำหรับแต่ละคำใน strcin: แทรกคำลงท้าย words
• กำหนด map p2i
• i := 0, pat := สตริงว่าง
• สำหรับ c ใน pattern: ถ้า c ไม่ใช่สมาชิกของ p2i: เพิ่ม i ขึ้น 1, p2i[c] := i; pat := pat ต่อ p2i[c]
• กำหนด map str2i
• i := 0, pat1 := สตริงว่าง
• สำหรับ c ใน words: ถ้า c ไม่ใช่สมาชิกของ str2i: เพิ่ม i ขึ้น 1, str2i[c] := i; pat1 := pat1 ต่อ str2i[c]
• คืนค่า true เมื่อ pat1 เท่ากับ pat

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    bool wordPattern(string pattern, string str) {
        istringstream strcin(str);
        string word;
        vector<string> words;
        while (strcin >> word) words.push_back(word);
        unordered_map<char, int> p2i;
        int i = 0;
        string pat = "";
        for (auto c : pattern) {
            if (p2i.count(c) == 0) {
                i++;
                p2i[c] = i;
            }
            pat += to_string(p2i[c]);
        }
        unordered_map<string, int> str2i;
        i = 0;
        string pat1 = "";
        for (auto c : words) {
            if (str2i.count(c) == 0) {
                i++;
                str2i[c] = i;
            }
            pat1 += to_string(str2i[c]);
        }
        return pat1 == pat;
    }
};
main() {
    Solution ob;
    cout << (ob.wordPattern("cbbc", "word pattern pattern word"));
}

อินพุต

"cbbc", "word pattern pattern word"

เอาต์พุต

1