Giả sử chúng ta có một chuỗi gen. Chuỗi đó có thể được biểu diễn bằng một chuỗi có độ dài 8, chuỗi này bao gồm các chữ cái [A, C, G, T]. Bây giờ xem xét chúng ta muốn điều tra về một đột biến, nơi MỘT đột biến thực sự là MỘT ký tự đơn thay đổi trong chuỗi gen. Ví dụ, "AACCGTTT" thay đổi thành "AACCGTTA" là 1 đột biến.
Chúng ta cũng có một "ngân hàng" gen cho trước, nơi chứa tất cả các đột biến gen hợp lệ. Một gen phải có trong ngân hàng mới trở thành chuỗi gen hợp lệ.
Bây giờ giả sử chúng ta có 3 thứ cho trước - start, end, bank, nhiệm vụ của chúng ta là xác định số lượng đột biến tối thiểu cần thiết để đột biến từ "start" sang "end". Nếu không thể chuyển đổi từ start sang end, trả về -1.
Vì vậy, nếu đầu vào giống như start = "AACCGGTT", end = "AAACGGTA", bank = ["AACCGGTA", "AACCGCTA", "AAACGGTA"], thì đầu ra sẽ là 2.
Để giải quyết bài toán này, chúng ta sẽ làm theo các bước sau −
Định nghĩa hàm putStar(), nhận s,
Định nghĩa mảng ret
for khởi tạo i := 0, khi i ≪ kích thước của s, cập nhật (tăng i lên 1), thực hiện −
temp := chuỗi con của s từ 0 đến i-1 nối "*" + chuỗi con của s từ chỉ số i + 1 đến cuối
chèn temp vào cuối ret
trả về ret
Từ phương thức main thực hiện như sau −
Định nghĩa một map gọi là graph.
for khởi tạo i := 0, khi i < kích thước của bank, cập nhật (tăng i lên 1), thực hiện −
s := bank[i]
out = putStar(bank[i])
for khởi tạo j := 0, khi j < kích thước của out, cập nhật (tăng j lên 1), thực hiện
chèn s vào cuối graph[out[j]]
Định nghĩa một hàng đợi q
chèn start vào q
Định nghĩa một tập hợp visited
chèn start vào visited
for khởi tạo lvl := 1, khi q không rỗng, cập nhật (tăng lvl lên 1), thực hiện −
sz := kích thước của q
khi sz khác 0, giảm sz mỗi lần lặp, thực hiện −
node := phần tử đầu của q
xóa phần tử khỏi q
out = putStar(node)
for khởi tạo i := 0, khi i < kích thước của out, cập nhật (tăng i lên 1), thực hiện−
u := out[i]
for khởi tạo j := 0, khi j < kích thước của graph[u], cập nhật (tăng j lên 1), thực hiện −
v := graph[u, j]
nếu vi có trong visited, thì thoát khỏi vòng lặp
nếu v bằng end, thì trả về lvl
chèn v vào visited
chèn v vào q
trả về -1
Hãy xem triển khai sau để hiểu rõ hơn −
Ví dụ
#include <bits/stdc++.h> using namespace std; class Solution { public: vector <string> putStar(string s){ vector <string> ret; for(int i = 0; i < s.size(); i++){ string temp = s.substr(0, i) + "*" + s.substr(i + 1); ret.push_back(temp); } return ret; } int minMutation(string start, string end, vector<string>& bank) { unordered_map < string, vector <string> > graph; for(int i = 0; i < bank.size(); i++){ string s = bank[i]; vector <string> out = putStar(bank[i]); for(int j = 0; j < out.size(); j++){ graph[out[j]].push_back(s); } } queue <string> q; q.push(start); set <string> visited; visited.insert(start); for(int lvl = 1; !q.empty(); lvl++){ int sz = q.size(); while(sz--){ string node = q.front(); q.pop(); vector <string> out = putStar(node); for(int i = 0; i < out.size(); i++){ string u = out[i]; for(int j = 0; j < graph[u].size(); j++){ string v = graph[u][j]; if(visited.count(v)) continue; if(v == end) return lvl; visited.insert(v); q.push(v); } } } } return -1; } }; main(){ Solution ob; vector<string> v = {"AACCGGTA", "AACCGCTA", "AAACGGTA"}; cout << (ob.minMutation("AACCGGTT", "AAACGGTA", v)); }Đầu vào
"AACCGGTT", "AAACGGTA", {"AACCGGTA", "AACCGCTA", "AAACGGTA"}Đầu ra
2