LeetCode 126 单词接龙 II

这道题是给出起始的单词和最终的单词，再给出一个单词列表，问从起始的单词转换成最终的单词最少需要转换次数的步骤，可能有多个符合要求的答案，都要输出。如果两个单词只有一位的字母不同，则这两个单词可以转换。思路就是首先用map把单词都映射为int，然后把每个单词看作一个点，两个可以互相转换的单词连一条线，就构成了图，如果最终的单词不在图里可以直接输出。接下来就是难点了，因为这道题本质就是求最短路径，但是有可能有多条最短路径。我首先尝试了dfs回溯，结果超时，又进行剪枝，还是超时，又试了一些bfs改进打的方法，都是超时。看了题解，才知道用改进的bellman-ford可以求出，把数列中保存的点改成保存点的数组，这就相当于记录了路径，如果数组最后一个元素是最终的单词，即可把这个数组添加到答案，因为这个算法已经可以保证路径最短。

class Solution {
public:

    vector> findLadders(string beginWord, string endWord, vector& wordList) {
        int sz=wordList.size(),len=beginWord.size();
        vector G[sz+5];
        vector > ans;
        unordered_map mp;
        unordered_map cg;
        int vis[sz+5],d[sz+5];
        memset(vis,0,sizeof(0));
        int cnt = 1;
        mp[beginWord]=cnt++;
        cg[cnt-1]=beginWord;
        for(int i=0;i1) break;
            }
            if(ok==1) G[1].push_back(mp[wordList[i]]);
        }
        for(int i=0;i1) break;
                        }
                        if(ok==1) 
                        {
                            G[mp[wordList[i]]].push_back(mp[wordList[j]]);
                            G[mp[wordList[j]]].push_back(mp[wordList[i]]);
                        }
                    }
        if(!mp[endWord]) return ans;
        memset(d,0x3f3f3f3f,sizeof(d));
        vector v,now;
        v.push_back(1);
        queue > q;
        d[1]=0;
        q.push(v);
        int goal = mp[endWord];
        while(!q.empty())
        {
            now=q.front();q.pop();
            int b=now.back();
            if(b==goal)
            {
                vector vs;
                for(int i=0;i=d[b]+1)
                {
                    d[v]=d[b]+1;
                    vector tmp(now);
                    tmp.push_back(v);
                    q.push(tmp);
                }
            }
        }
        return ans;
    }
};