boolnear(string& a, string& b){ int i = 0, diff = 0, n = a.length(); while(i < n and diff <= 1) { if(a[i] != b[i]) diff++; i++; } return i == n and diff == 1; }
intshortestLadderLength(string beginWord, string endWord, vector<string> &wordList){ unordered_map<string, vector<string>> adj; int n = wordList.size(); for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { if(near(wordList[i], wordList[j])) { adj[wordList[i]].push_back(wordList[j]); adj[wordList[j]].push_back(wordList[i]); } } if(near(wordList[i], beginWord)) { adj[wordList[i]].push_back(beginWord); adj[beginWord].push_back(wordList[i]); } if(near(wordList[i], endWord)) { adj[wordList[i]].push_back(endWord); adj[endWord].push_back(wordList[i]); } } if(near(beginWord, endWord)) { return2; } unordered_set<string> vis{beginWord}; queue<string> q; q.push(beginWord); int res = 2; while(!q.empty()) { int sz = q.size(); while(sz--) { auto u = q.front(); q.pop(); for(auto& v : adj[u]) { if(vis.count(v)) continue; vis.insert(v); q.push(v); if(v == endWord) return res; } } res++; } return0; }