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

โปรแกรมหาค่า K สำหรับ K-Similar Strings ใน C++


สมมติว่าเรามีสองสตริง s และ t สตริงทั้งสองนี้เป็น K-similar เมื่อเราสามารถสลับตำแหน่งของตัวอักษรสองตัวใน s ตรง K ครั้งเพื่อให้สตริงผลลัพธ์เป็น t เรามีแอนนาแกรมสองตัว s และ t และเราต้องหา K ที่เล็กที่สุดที่ s และ t เป็น K-similar

ดังนั้น หากอินพุตเป็น s ="abc", t ="bac" ผลลัพธ์จะเป็น 1

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

  • กำหนดฟังก์ชัน swapp() ซึ่งจะใช้สตริง s, i, j,

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

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

  • จากวิธีหลัก ให้ทำดังต่อไปนี้ −

  • ถ้า A เหมือนกับ B ดังนั้น:ให้คืนค่า 0

  • กำหนดการเยี่ยมชมหนึ่งชุด

  • ใส่ A เข้าไป

  • กำหนดหนึ่งคิว q แทรก A ลงใน q

  • สำหรับการเริ่มต้น lvl :=1 เมื่อไม่มี q ว่าง ให้อัปเดต (เพิ่ม lvl ขึ้น 1) ทำ -

    • sz :=ขนาดของ q

    • ในขณะที่ sz ไม่ใช่ศูนย์ ให้ลด sz ลง 1 ในการวนซ้ำแต่ละครั้ง ทำ:

      • curr :=องค์ประกอบแรกของ q

      • ลบองค์ประกอบออกจาก q

      • ผม :=0

      • ในขณะที่ (i <ขนาดของ curr และ curr[i] เท่ากับ B[i]) ทำ

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

      • สำหรับการเริ่มต้น j :=i + 1 เมื่อ j <ขนาดของ curr ให้อัปเดต (เพิ่ม j ขึ้น 1) ให้ทำ

        • ถ้า curr[i] เหมือนกับ curr[j] แล้ว:

          • ละเว้นส่วนต่อไปนี้ ข้ามไปยังการทำซ้ำถัดไป

        • ถ้า curr[j] ไม่เท่ากับ B[i] แล้ว:

          • ละเว้นส่วนต่อไปนี้ ข้ามไปยังการทำซ้ำถัดไป

        • ถ้า curr[j] เหมือนกับ B[j] แล้ว:

          • ละเว้นส่วนต่อไปนี้ ข้ามไปยังการทำซ้ำถัดไป

        • swapp(curr, i, j)

        • ถ้าสกุลเงินเหมือนกับ B แล้ว:

          • กลับเลเวล

        • หากไม่นับการเรียก (curr) ของการเยี่ยมชมแล้ว:

          • ใส่เคอร์เนลเข้าที่เข้าชมแล้ว

          • ใส่เคอร์เนลลงใน q

        • swapp(curr, i, j)

  • กลับ -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