120.word-ladder.md

120. 单词接龙

• 题型：单源-无权图-最短路（边的权重为1）
• 出处
• 描述 给出两个单词（start和end）和一个字典，找出从start到end的最短转换序列，输出最短序列的长度。 变换规则如下： 每次只能改变一个字母。 变换过程中的中间单词必须在字典中出现。(起始单词和结束单词不需要出现在字典中) 如果不存在这样的转换序列，返回0。 所有单词具有相同的长度。 所有单词只由小写字母组成。 字典中不存在重复的单词。 你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
• 实现

class Solution {
public:
    int ladderLength(string &start, string &end, unordered_set<string> &dict) {
        //题目说起始词和结束词不一定在dict里，那么干脆把2个词都加进来
        dict.insert(start);
        dict.insert(end);
        
        //len表示start与dict里其他每个单词之间的距离（转换长度）；
        //还可以表示是否被访问过：INT_MAX表示未被访问。
        map<string, int>len;   
        for(auto w:dict)    len[w] = INT_MAX;
        len[start] = 0;

        //先把start加入队列里。
        queue<string>Q;
        Q.push(start);
        
        string cur;  //cur保存每次队列里的首元素
        while(!Q.empty())   // BFS
        {
            cur = Q.front();
            Q.pop();
            
            for(auto w:dict)
            {   //  在dict里，寻找未被访问的cur的邻接点（与cur相差一个字符的单词）。
                if(dif(cur, w)==1 && len[w]==INT_MAX)
                {
                    //更新距离。这里和“单源最短路-无权图（边的权重是1）一样的思路”
                    len[w] = len[cur] +1;   
                    Q.push(w);
                }
            }
            
        }
        
        // 如果图不连通，则无解返回0。
        return len[end]==INT_MAX? 0: len[end]+1;        
    }
        
    // 两个单词相差一个字符，可视作一对邻接点
    int dif(string s1, string s2)
    {
        int d = 0, i;        
        for(i=0; i<s1.size(); i++)
        {
            if(s1[i]!=s2[i])
                d++;
        }
        return d;
    }
};