C++ में K-समान स्ट्रिंग्स के लिए K का मान खोजने का प्रोग्राम

मान लीजिए हमारे पास दो स्ट्रिंग्स s और t हैं। ये दो स्ट्रिंग्स K-समान हैं जब हम s में दो अक्षरों की पोजीशन को स्वैप करके ठीक K बार कर सकते हैं ताकि परिणामी स्ट्रिंग t हो। हमारे पास दो एनाग्राम s और t हैं, और हमें सबसे छोटा K ढूंढना है जिसके लिए s और t K-समान हैं।

उदाहरण के लिए, यदि इनपुट s = "abc", t = "bac" है, तो आउटपुट 1 होगा।

हल करने के चरण

swapp() फ़ंक्शन परिभाषित करें, यह स्ट्रिंग s, i, j लेगा:
- x := s[i], y := s[j]
- s[i] := y, s[j] := x
मुख्य मेथड से निम्नलिखित करें:
- यदि A == B, तो 0 वापस करें।
- एक सेट visited परिभाषित करें।
- A को visited में डालें।
- एक क्यू q परिभाषित करें, A को q में डालें।
- lvl := 1 से इनिशियलाइज़ करें, जब q खाली न हो, lvl को 1 से बढ़ाते हुए लूप चलाएं:
  - sz := q का आकार
  - sz नॉन-जीरो होने तक, प्रत्येक इटरेशन में sz को 1 से घटाते हुए व्हाइल लूप चलाएं:
    - curr := q का पहला एलिमेंट
    - q से एलिमेंट हटाएं
    - i := 0
    - i < curr.size() और curr[i] == B[i] तक व्हाइल लूप चलाएं:
      - i++
    - j := i + 1 से इनिशियलाइज़ करें, जब j < curr.size(), j++ करते हुए लूप चलाएं:
      - यदि curr[i] == curr[j], तो अगले इटरेशन पर जाएं।
      - यदि curr[j] != B[i], तो अगले इटरेशन पर जाएं।
      - यदि curr[j] == B[j], तो अगले इटरेशन पर जाएं।
      - swapp(curr, i, j)
      - यदि curr == B, तो lvl वापस करें।
      - यदि visited में curr नहीं है, तो:
        
        curr को visited में डालें
        
        curr को q में डालें
      - swapp(curr, i, j)
- -1 वापस करें।

उदाहरण

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

#include 
using namespace std;
class Solution {
public:
    int kSimilarity(string A, string B) {
        if (A == B)
            return 0;
        unordered_set visited;
        visited.insert(A);
        queue 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;
    }
};
int main(){
    Solution ob;
    cout << (ob.kSimilarity("abc", "bac"));
}

इनपुट

"abc", "bac"