字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列：

序列中第一个单词是 beginWord 。
序列中最后一个单词是 endWord 。
每次转换只能改变一个字母。
转换过程中的中间单词必须是字典 wordList 中的单词。
给你两个单词 beginWord 和 endWord 和一个字典 wordList ，找到从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0。

  示例 1：

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：5
解释：一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。

示例 2：

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
输出：0
解释：endWord "cog" 不在字典中，所以无法进行转换。

提示：

• 1 <= beginWord.length <= 10
• endWord.length == beginWord.length
• 1 <= wordList.length <= 5000
• wordList[i].length == beginWord.length
• beginWord、endWord 和 wordList[i] 由小写英文字母组成
• beginWord != endWord
• wordList 中的所有字符串 互不相同

参考答案

typedef unsigned int uint;
const int N=5005,L0=10,L=N*4; const uint mul=131;
int vis[N],q[N],v1; uint hsh[N],mul1[L0];
vector<int> v[L];
namespace Hash{
	const uint S=16,S1=32-S,M=1996090921;
	struct node{
		int x,t;
		vector<int> *y;
	}h[(1<<S)+1005];
	int T=1;
	inline void insert(int x,int y){
		node *p=h+((uint)x*M>>S1);
		for (;p->t==T;++p)
			if (p->x==x){p->y->push_back(y); return;}
		p->t=T; p->x=x; p->y=v+(v1++); p->y->push_back(y);
	}
	inline vector<int>** find(int x){
		for (node *p=h+((uint)x*M>>S1);p->t==T;++p)
			if (p->x==x)return &p->y;
		return 0;
	}
} using namespace Hash;

class Solution {
public:
	int ladderLength(string beginWord, string endWord, vector<string>& w) {
		for (int i=0;i<v1;++i)v[i].clear();
		int n=w.size(); v1=0; ++T;
		for (int i=0;i<n-1;++i)
			if (w[i]==endWord)swap(w[i],w[n-1]);
		if (w[n-1]!=endWord)return 0;
		w.push_back(beginWord); ++n;
		mul1[0]=1; for (int i=1;i<L0;++i)mul1[i]=mul1[i-1]*mul;
		for (int i=0;i<n;++i){
			int l=w[i].size(); uint h0=0;
			for (char *p=&w[i][0],*end=p+l;p!=end;++p)h0=h0*mul+*p;
			for (char *p=&w[i][0],*end=p+l;p!=end;++p){
				uint h1=h0-*p*mul1[end-1-p];
				insert(h1,i);
			}
			hsh[i]=h0;
		}
		for (int i=0;i<n;++i)vis[i]=0; vis[n-1]=1;
		int l=0,r=1,ans=1; q[0]=n-1;
		while (l<r){
			int r1=r; ++ans;
			for (;l<r;++l){
				int i=q[l]; uint h0=hsh[i];
				for (char *p=&w[i][0],*end=p+w[i].size();p!=end;++p){
					uint h1=h0-*p*mul1[end-1-p];
					vector<int>** pt=find(h1);
					if (*pt){
						vector<int> &vec=*(*pt);
						for (int j:vec)
							if (!vis[j]){
								q[r1++]=j,vis[j]=1;
								if (j==n-2)return ans;
							}
						*pt=0;
					}
				}
			}
			l=r; r=r1;
		}
		return 0;
	}
};