leetcode 433. Minimum Genetic Mutation 最少遗传变异次数 + 和Word Ladder一样BFS + 反向链表 + DFS

Love The Way You Lie 2022-06-04 10:14 89阅读 0赞

A gene string can be represented by an 8-character long string, with choices from “A”, “C”, “G”, “T”.

Suppose we need to investigate about a mutation (mutation from “start” to “end”), where ONE mutation is defined as ONE single character changed in the gene string.

For example, “AACCGGTT” -> “AACCGGTA” is 1 mutation.

Also, there is a given gene “bank”, which records all the valid gene mutations. A gene must be in the bank to make it a valid gene string.

Now, given 3 things - start, end, bank, your task is to determine what is the minimum number of mutations needed to mutate from “start” to “end”. If there is no such a mutation, return -1.

Note:

Starting point is assumed to be valid, so it might not be included in the bank.  
If multiple mutations are needed, all mutations during in the sequence must be valid.  
You may assume start and end string is not the same.  
Example 1:

start: “AACCGGTT”  
end: “AACCGGTA”  
bank: \[“AACCGGTA”\]

return: 1  
Example 2:

start: “AACCGGTT”  
end: “AAACGGTA”  
bank: \[“AACCGGTA”, “AACCGCTA”, “AAACGGTA”\]

return: 2  
Example 3:

start: “AAAAACCC”  
end: “AACCCCCC”  
bank: \[“AAAACCCC”, “AAACCCCC”, “AACCCCCC”\]

return: 3

题意很简单，和[leetcode 126. Word Ladder II BFS + 反向链表 + DFS][leetcode 126. Word Ladder II BFS _ _ _ DFS] 和 [leetcode 127. Word Ladder BFS广度优先遍历][leetcode 127. Word Ladder BFS] 一样的做法，建议一起学习

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <cmath>
    
    using namespace std;
    
    
    class Solution
    {
    public:
        int minMutation(string beginWord, string endWord, vector<string>& wordList)
        {
            set<string> wordSet(wordList.begin(), wordList.end());
            if (wordSet.find(beginWord) != wordSet.end())
                wordSet.erase(beginWord);
    
            queue<string> que;
            map<string, int> mp;
            int level = 1;
            que.push(beginWord);
            mp[beginWord] = level;
            while (que.empty() == false)
            {
                string now = que.front();
                que.pop();
                int level = mp[now];
                for (int i = 0; i < now.length(); i++)
                {
                    string tmp = now;
                    string change = "ACGT";
                    for (char j : change)
                    {
                        tmp[i] = j;
                        if (wordSet.find(tmp) != wordSet.end())
                        {
                            if (tmp == endWord)
                                return level;
                            else
                            {
                                que.push(tmp);
                                wordSet.erase(tmp);
                                mp[tmp] = level + 1;
                            }
    
                        }
                    }
                }
            }
            return -1;
        }
    };

也可以这么做

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    #include <iomanip>
    #include <cstdlib>
    #include <ctime>
    #include <array>
    using namespace std;
    
    
    
    class Solution {
    public:
        int minMutation(string start, string end, vector<string>& bank)
        {
            set<string> dict(bank.begin(), bank.end());
            if (dict.find(start) != dict.end())
                dict.erase(start);
    
            queue<string> que;
            que.push(start);
            set<string> visit;
            visit.insert(start);
            int lev = 0;
            while (que.empty() == false)
            {
                queue<string> next;
                int size = que.size();
                for (int i = 0; i < size; i++)
                {
                    string top = que.front();
                    que.pop();
    
                    string change = "ACGT";
                    for (int i = 0; i < top.length(); i++)
                    {
                        string tmp = top;
                        for (char c : change)
                        {
                            tmp[i] = c;
                            if (dict.find(tmp) != dict.end())
                            {
                                if (tmp == end)
                                    return lev + 1;
                                else
                                {
                                    next.push(tmp);
                                    dict.erase(tmp);
                                }
                            }
                        }
                    }
                }
                lev++;
                que = next;
            }
            return -1;
        }
    };

[leetcode 126. Word Ladder II BFS _ _ _ DFS]: http://blog.csdn.net/jackzhang_123/article/details/78002641
[leetcode 127. Word Ladder BFS]: http://blog.csdn.net/jackzhang_123/article/details/78002561