[数据结构与算法]leetcode BFS(python+c++)

1.最小基因变化

思路：bfs搜索回溯

python:?

class Solution:
    def minMutation(self, start: str, end: str, bank: List[str]) -> int:
        library = ['A','C', 'G','T']
        queue = [start]
        num = 0
        vis = set()
        while queue:
            size = len(queue)
            for i in range(size):
                cur = queue.pop(0)
                if cur == end:
                    return num                
                for j in range(len(cur)):
                    for letter in library:
                        temp = cur[:j] + letter +cur[j+1:]
                        if temp in bank and temp not in vis:
                            queue.append(temp)
                            vis.add(temp)
            num += 1
        return -1

c++:

class Solution {
public:
    int minMutation(string start, string end, vector<string>& bank) {
        string library = "ACGT";
        queue<string> queue_;
        queue_.push(start);
        int num = 0;
        unordered_set<string> vis;
        while(!queue_.empty()){
            int size = queue_.size();
            for(int i = 0; i < size; i++){
                string cur = queue_.front();
                queue_.pop();
                if(cur == end){
                    return num;
                }
                for(int j = 0; j < cur.size(); j++){
                    for(auto letter : library){
                        string temp = cur.substr(0, j) + letter + cur.substr(j+1, cur.size() - j - 1);
                        // cout<<temp<<endl;
                        if(std::find(bank.begin(), bank.end(), temp) != bank.end() && 
                        vis.find(temp) == vis.end()){
                            queue_.push(temp);
                            vis.insert(temp);
                        }
                    }
                }
            }
            num ++ ;
        }
        return -1;
    }
};