C++ में K-समान स्ट्रिंग्स

मान लीजिए कि हमारे पास दो तार ए और बी हैं। ये दो तार के-समान हैं (जहां के एक गैर-ऋणात्मक पूर्णांक है) यदि हम दो अक्षरों की स्थिति को ए में बिल्कुल के समय में स्वैप कर सकते हैं ताकि परिणामी स्ट्रिंग बी हो। तो, हमारे पास है दो विपर्यय A और B, हमें सबसे छोटा K ज्ञात करना है जिसके लिए A और B K-समान हैं।

इसलिए, यदि इनपुट A ="abc", B ="bac" जैसा है, तो आउटपुट 2 होगा।

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

• फ़ंक्शन स्वैप () को परिभाषित करें, यह स्ट्रिंग s, i, j,

  लेगा

• एक्स:=एस[i], वाई:=एस[जे]

• s[i] :=y, s[j] :=x

• मुख्य विधि से निम्न कार्य करें -

• अगर ए, बी के समान है, तो:, 0 लौटाएं

• देखे गए एक सेट को परिभाषित करें

• विज़िट किए गए में A डालें

• एक कतार q को परिभाषित करें, A को q में डालें

• lvl को इनिशियलाइज़ करने के लिए:=1, जब q खाली न हो, तो अपडेट करें (lvl को 1 से बढ़ाएँ), करें -

  • sz :=q का आकार

  • जबकि sz गैर-शून्य है, प्रत्येक पुनरावृत्ति में sz को 1 से घटाएं, करें -

    • curr :=q का पहला तत्व

    • q से तत्व हटाएं

    • मैं :=0

    • जबकि (i

      • (मैं 1 से बढ़ाइए)

    • इनिशियलाइज़ j :=i + 1 के लिए, जब j

      • अगर curr[i], curr[j] के समान है, तो -

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

      • अगर curr[j] B[i] के बराबर नहीं है, तो -

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

      • अगर curr[j] B[j] के समान है, तो -

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

      • स्वैप (करंट, आई, जे)

      • यदि curr B के समान है, तो -

        • वापसी एलवीएल

      • यदि विज़िट की गई कॉल काउंट (कर) नहीं है, तो -

        • विज़िट किए गए में curr डालें

        • क्यू में कर्व डालें

      • स्वैप (करंट, आई, जे)

• वापसी -1

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

उदाहरण

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int kSimilarity(string A, string B) {
      if (A == B)
      return 0;
      unordered_set<string> visited;
      visited.insert(A);
      queue<string> q;
      q.push(A);
      for (int lvl = 1; !q.empty(); lvl++) {
         int sz = q.size();
         while (sz--) {
            string curr = q.front();
            q.pop();
            int i = 0;
            while (i < curr.size() && curr[i] == B[i])
            i++;
            for (int j = i + 1; j < curr.size(); j++) {
               if (curr[i] == curr[j])
               continue;
               if (curr[j] != B[i])
               continue;
               if (curr[j] == B[j])
               continue;
               swapp(curr, i, j);
               if (curr == B)
               return lvl;
               if (!visited.count(curr)) {
                  visited.insert(curr);
                  q.push(curr);
               }
               swapp(curr, i, j);
            }
         }
      }
      return -1;
   }
   void swapp(string &s, int i, int j) {
      char x = s[i];
      char y = s[j];
      s[i] = y;
      s[j] = x;
   }
};
main(){
   Solution ob;
   cout << (ob.kSimilarity("abc", "bac"));
}

इनपुट

"abc", "bac"

आउटपुट

1