Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

वर्ड पैटर्न II - C++


मान लीजिए हमारे पास एक पैटर्न और str नामक एक स्ट्रिंग है, हमें जांचना होगा कि क्या str उसी पैटर्न का अनुसरण करता है या नहीं। यहां पैटर्न का अनुसरण करने का अर्थ है पूर्ण मिलान, जैसे कि पैटर्न में एक अक्षर और str में एक गैर-खाली सबस्ट्रिंग के बीच एक बायजेक्शन हो।

तो, यदि इनपुट पैटर्न "abaa" है, str "orangegreenorangeorange" है, तो आउटपुट true होगा

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −

  • solve() नामक एक फ़ंक्शन परिभाषित करें, जो i, j, ptr, s, एक मैप m, used नामक एक सेट लेगा,

  • यदि i >= s का आकार और j >= ptr का आकार, तो −

    • true लौटाएं

  • यदि i >= s का आकार या j >= ptr का आकार, तो −

    • false लौटाएं

  • यदि ptr[j], m में है, तो −

    • req := m[ptr[j]]

    • len := req का आकार

    • यदि len, s के आकार से अधिक है, तो −

      • false लौटाएं

    • यदि इंडेक्स (i से len-1) से s का सबस्ट्रिंग req के समान है और solve(i + len, j + 1, ptr, s, m, used), तो −

      • true लौटाएं

    • false लौटाएं

  • अन्यथा

    • x := ptr[j]

    • k := i से आरंभ करें, जब k, s के आकार से कम, अद्यतन करें (k को 1 से बढ़ाएं), करें −

      • temp := इंडेक्स (i से k - i) से s का सबस्ट्रिंग

      • यदि temp, used में है, तो −

        • निम्नलिखित भाग को अनदेखा करें, अगले पुनरावृत्ति पर जाएं

      • m[x] := temp

      • temp को used में डालें

      • यदि solve(k + 1, j + 1, ptr, s, m, used), तो −

        • true लौटाएं

      • m से x हटाएं

      • used से temp हटाएं

  • false लौटाएं

  • मुख्य विधि से निम्नलिखित करें −

  • एक मैप m परिभाषित करें

  • एक सेट used परिभाषित करें

  • solve(0, 0, ptr, s, m, used) लौटाएं

उदाहरण 

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें −

#include <bits/stdc++.h> using namespace std; class Solution { public:    bool solve(int i, int j, string ptr, string s, map <char, string>& m, set<string>& used){       if (i >= s.size() && j >= ptr.size()) {          return true;       }       if (i >= s.size() || j >= ptr.size())          return false;       if (m.count(ptr[j])) {          string req = m[ptr[j]];          int len = req.size();          if (len > s.size() - i)             return false;          if ((s.substr(i, len) == req) && solve(i + len, j + 1, ptr, s, m, used))             return true;          return false;       }       else {          char x = ptr[j];          for (int k = i; k < s.size(); k++) {             string temp = s.substr(i, k - i + 1);             ;             if (used.count(temp))                continue;             m[x] = temp;             used.insert(temp);             if (solve(k + 1, j + 1, ptr, s, m, used))                return true;             m.erase(x);             used.erase(temp);          }       }       return false;    }    bool wordPatternMatch(string ptr, string s) {       map<char, string> m;       set<string> used;       return solve(0, 0, ptr, s, m, used);    } }; main(){    Solution ob;    cout << (ob.wordPatternMatch("abaa", "orangegreenorangeorange")); }

इनपुट

"abaa" "orangegreenorangeorange"

आउटपुट

1

  1. C++ में BK ट्री परिचय C++ में BK ट्री परिचय

    BK ट्री या बर्कहार्ड ट्री (Burkhard tree) एक प्रकार की डेटा संरचना है जिसका उपयोग आमतौर पर लेवेंश्टाइन दूरी (Levenshtein distance) के आधार पर स्पेल चेक करने के लिए किया जाता है। इसका उपयोग स्ट्रिंग मिलान के लिए ऑटोकरेक्ट फीचर बनाने के लिए भी किया जाता है। मान लें कि हमारे पास एक डिक्शनरी में कुछ शब

  1. C++ में कम्पोजिट डिज़ाइन पैटर्न C++ में कम्पोजिट डिज़ाइन पैटर्न

    कम्पोजिट पैटर्न का उपयोग वहां किया जाता है जहां हमें ऑब्जेक्ट्स के एक समूह को एक सिंगल ऑब्जेक्ट के समान तरीके से ट्रीट करने की आवश्यकता होती है। कम्पोजिट पैटर्न ऑब्जेक्ट्स को ट्री स्ट्रक्चर के रूप में कंपोज करता है ताकि पार्ट और होल हायरार्की दोनों को दर्शाया जा सके। इस प्रकार का डिज़ाइन पैटर्न स्ट्

  1. - C++ सिंगलटन डिज़ाइन पैटर्न समझाया गया

    सिंगलटन डिज़ाइन पैटर्न एक सॉफ्टवेयर डिज़ाइन सिद्धांत है जिसका उपयोग क्लास के इंस्टेंटिएशन को एक ऑब्जेक्ट तक सीमित करने के लिए किया जाता है। यह तब उपयोगी होता है जब सिस्टम भर में कार्यों को समन्वयित करने के लिए ठीक एक ऑब्जेक्ट की आवश्यकता होती है। उदाहरण के लिए, यदि आप एक लॉगर का उपयोग कर रहे हैं जो