Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

โปรแกรมตรวจสอบคำที่กำหนดว่ายังคงรูปแบบที่กำหนดหรือไม่ใน C++


สมมติว่าเรามีรูปแบบ p และสตริง 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 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