โปรแกรมหาจำนวนกลุ่มการกลายพันธุ์ของยีนทั้งหมดใน C++

สมมติว่าเรามีรายการสตริงชื่อ genes โดยแต่ละอิลิเมนต์มีความยาวเท่ากันและประกอบด้วยตัวอักษร "A", "C", "G" และ/หรือ "T" มีกฎดังนี้:

• เมื่อสตริงสองตัว s1 และ s2 เหมือนกันทุกตัวอักษรยกเว้นหนึ่งตัว s1 และ s2 อยู่ในกลุ่มกลายพันธุ์เดียวกัน
• เมื่อ s1 และ s2 อยู่ในกลุ่มเดียวกัน และ s2 และ s3 อยู่ในกลุ่มเดียวกัน แล้ว s1 และ s3 ก็อยู่ในกลุ่มเดียวกัน (สมบัติการรุ้ง)

เราต้องหาจำนวนกลุ่มกลายพันธุ์ทั้งหมดที่สามารถสร้างได้

เช่น หากอินพุตคือ genes = ["ACGT", "ACGC", "ACTT", "TTTT", "TGTT"] ผลลัพธ์จะเป็น 2 กลุ่มคือ ["ACGT", "ACGC", "ACTT"] และ ["TTTT", "TTTG"]

ขั้นตอนการแก้ปัญหา

• ใช้ Union-Find (Disjoint Set Union) จัดการกลุ่ม
• ฟังก์ชัน getPar(a): หา parent พร้อม Path Compression
• ฟังก์ชัน unite(a, b): รวมกลุ่ม ถ้าต่างกลุ่ม
• ฟังก์ชัน ok(a, b): ตรวจสอบว่าต่างกันแค่ 1 ตัวอักษรหรือไม่
• จัดเรียงอาร์เรย์ สร้าง set สำหรับค้นหาเร็ว
• สำหรับแต่ละสตริง ลองเปลี่ยนตัวอักษรแต่ละตำแหน่งเป็น A, C, G, T ถ้าสตริงใหม่อยู่ใน set ให้ unite
• คืนค่าจำนวนกลุ่มที่เหลือ

ตัวอย่างโค้ด

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    map<string, string> parent;
    string getPar(string& a) {
        if (parent[a] == a) return a;
        return parent[a] = getPar(parent[a]);
    }
    bool unite(string& a, string& b) {
        string parA = getPar(a);
        string parB = getPar(b);
        if (parA != parB) {
            parent[parA] = parB;
            return true;
        }
        return false;
    }
    bool ok(string& a, string& b) {
        int cnt = 0;
        for (int i = 0; i < a.size(); i++)
            cnt += a[i] != b[i];
        return cnt == 1;
    }
    int solve(vector<string> v) {
        sort(v.begin(), v.end());
        set<string> s(v.begin(), v.end());
        int ret = v.size();
        for (auto& it : v) parent[it] = it;
        for (auto& it : v) {
            for (int j = 0; j < it.size(); j++) {
                string temp = it;
                for (char x : {'A', 'C', 'G', 'T'}) {
                    if (x != it[j]) {
                        temp[j] = x;
                        if (s.count(temp)) {
                            if (unite(temp, it)) ret--;
                        }
                    }
                }
            }
        }
        return ret;
    }
};

int main() {
    vector<string> v = {"ACGT", "ACGC", "ACTT", "TTTT", "TGTT"};
    Solution ob;
    cout << ob.solve(v);
}

อินพุต

{"ACGT", "ACGC", "ACTT", "TTTT", "TGTT"}

เอาต์พุต

2