LeetCode力扣第433题--《最小基因变化》题解---DFS+回溯

DFS起点为end，终点为start，从end回溯至start。

对于end，

• 若end为无效基因序列，则直接返回-1；
• 若end为有效基因序列，则进行DFS：存在路径（将会更新ans值）则返回ans，不存在路径（未更新ans值）则返回-1。

DFS算法思路：

        对于当前遍历基因序列结点end，遍历bank数组，寻找尚未加入到路径（即未访问）并且变换一次可到达的基因序列s（即可进行DFS的下一结点），将s加入到路径（即设为访问），路径数加一（即count+1），再进行DFS，对结点s进行完DFS遍历后，将结点移出路径（即从在vis中删除）。

DFS的结束存在两种情况：

•         一是start==end，这种情况为start在bank基因库中，并存在start到end的路径，那么我们只需判断当前路径数是否为变化次数最少路径 ，若是，则更新最少变化次数。
•         二是isValid(start,end)为真，即当前遍历结点下一步即可到达start，这种情况为无论start是否在bank基因库中，都存在start到end的路径，那么我们只需判断当前路径数+1是否为变化次数最少路径 ，若是，则更新最少变化次数。

最终代码如下：

class Solution {
private:
    unordered_map vis;//vis保存已访问的基因序列结点
    int ans=100;//ans为最少变化次数，初始设为最大
public:
    bool isValid(string a,string b){//判断a是否能变化到b
        int count=0;
        for(int i=0;i1) return false;
        }
        return true;
    }
    void DFS(string start, string end, vector& bank,int count){
        if(start==end){//这种情况为start在bank基因库中，并存在start到end的路径
            if(count& bank) {
        vector::iterator result=find(bank.begin(),bank.end(),end);
        if(result==bank.end()){//end为无效基因序列，返回-1
            return -1;
        }
        else{
            DFS(start,end,bank,0);
            if(ans==100) return -1;//未找到路径，返回-1
            else return ans;            
        }
    }
};

作者：kw8l8EILt1
链接：https://leetcode-cn.com/problems/minimum-genetic-mutation/solution/dfs-by-kw8l8eilt1-15ma/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。