康瑞部落

Word Ladder

Given two words (beginWord and endWord), and a dictionary, find the length of shortest transformation sequence from beginWord to endWord, such that:

1. Only one letter can be changed at a time

2. Each intermediate word must exist in the dictionary

For example,

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:

• Return 0 if there is no such transformation sequence.

• All words have the same length.

• All words contain only lowercase alphabetic characters.

解题思路：

第一的想法是用一个图来记录相邻关系，然后将问题转化成图的最短路径问题。

class Solution {
public:
    int ladderLength(string beginWord, string endWord, unordered_set<string>& wordDict) {
        if(beginWord == endWord){
            return 1;
        }
        if(isNeibor(beginWord, endWord)){
            return 2;
        }
        if(wordDict.find(beginWord)==wordDict.end()){
            wordDict.insert(beginWord);
        }
        if(wordDict.find(endWord)==wordDict.end()){
            wordDict.insert(endWord);
        }
        //将set转化成vector
        vector<string> wordVect;
        for(unordered_set<string>::iterator it = wordDict.begin(); it!=wordDict.end(); it++){
            wordVect.push_back(*it);
        }
        int len = wordVect.size();
        vector<vector<int>> graph(len, vector<int>());  //邻接表存储图
        int beginIndex = -1;
        int endIndex = -1;
        for(int i=0; i<len; i++){
            if(beginWord == wordVect[i]){
                beginIndex = i;
            }
            if(endWord == wordVect[i]){
                endIndex = i;
            }
            for(int j=i+1; j<len; j++){
                if(isNeibor(wordVect[i], wordVect[j])){
                    graph[i].push_back(j);
                    graph[j].push_back(i);
                }
            }
        }
        vector<int> pre(len, -1);       //某个节点的前驱节点
        pre[beginIndex] = beginIndex;
        queue<int> q({beginIndex});     //广度优先法
        bool flag = false;              //是否已经找到了路径
        while(!q.empty()){
            int c = q.front();
            q.pop();
            for(int i=0; i<graph[c].size(); i++){
                if(pre[graph[c][i]]<0){
                    pre[graph[c][i]] = c;
                    q.push(graph[c][i]);
                    if(graph[c][i]==endIndex){
                        flag = true;
                        break;
                    }
                }
            }
            if(flag){
                break;
            }
        }
        if(!flag){
            return 0;
        }
        int result = 1;
        int c = endIndex;
        while(pre[c]!=c){
            result++;
            c = pre[c];
        }
        return result;
    }
    
    bool isNeibor(const string& str1, const string& str2){
        int len = str1.length();
        if(len!=str2.length()){
            return false;
        }
        int c = 0;
        for(int i=0; i<len; i++){
            if(str1[i]!=str2[i]){
                c++;
            }
        }
        return c==1;
    }
};