水题，spfa即可
class Solution { public: vector<int> gra[5010]; int d[5010], vis[5010]; bool check(string str1, string str2) { int len1 = str1.length(), len2 = str2.length(); if(len1 != len2) return false; int cnt = 0; for(int i = 0; i < len1; i++) { if(str1[i] != str2[i]) cnt++; if(cnt > 1) return false; } return true; } int spfa(int s, int t) { for(int i = 0; i < 5010; i++) d[i] = 0x7fffffff; memset(vis, 0, sizeof(vis)); queue<int> Q; Q.push(s); vis[s] = 1; d[s] = 0; while(!Q.empty()) { int u = Q.front(); Q.pop(); vis[u] = 0; int len = gra[u].size(); for(int i = 0; i < len; i++) { int v = gra[u][i]; if(d[v] > d[u] + 1) { d[v] = d[u] + 1; if(!vis[v]) { Q.push(v); vis[v] = 1; } } } } if(d[t] == 0x7fffffff) return 0; return d[t] + 1; } int ladderLength(string beginWord, string endWord, vector<string>& wordList) { int n = wordList.size(); int s = 0, t = 0; for(int i = 0; i < n; i++) { if(wordList[i] == beginWord) s = i + 1; if(wordList[i] == endWord) t = i + 1; } if(s == 0) { s = n + 1; wordList.push_back(beginWord); n = wordList.size(); } for(int i = 0; i < n; i++) { for(int j = i + 1; j < n; j++) { if(check(wordList[i], wordList[j])) { gra[i + 1].push_back(j + 1); gra[j + 1].push_back(i + 1); } } } return spfa(s, t); } };