รูปแบบคำในภาษา C++

สมมติว่าเรามีรูปแบบและสตริง str ค้นหาว่า str ตามรูปแบบเดียวกันหรือไม่ ต่อไปนี้ หมายความว่ามีการ bijection ระหว่างตัวอักษรในรูปแบบและคำที่ไม่ว่างเปล่าใน str.

ดังนั้น หากอินพุตเป็นเหมือน pattern ="cbbc", str ="word pattern pattern word" ผลลัพธ์จะเป็น True

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• strcin :=str

• กำหนดอาร์เรย์ของคำ

• สำหรับแต่ละคำใน strcin

  • ใส่คำต่อท้ายคำ

• กำหนดหนึ่งแผนที่ p2i

• ผม :=0

• pat :=สตริงว่าง

• สำหรับรูปแบบ c -

  • ถ้า c ไม่ใช่สมาชิกของ p2i แล้ว −

    • (เพิ่ม i ขึ้น 1)

    • p2i[c] :=ฉัน

  • pat :=pat ต่อ p2i[c]

• กำหนดหนึ่งแผนที่ str2i

• ผม :=0

• pat1 :=สตริงว่าง

• สำหรับคในคำ -

  • ถ้า c ไม่ใช่สมาชิกของ str2i แล้ว −

    • (เพิ่ม i ขึ้น 1)

    • str2i[c] :=ฉัน

  • pat1 :=pat1 เชื่อม str2i[c]

• คืนค่า จริง เมื่อ 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