fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int dist(string a , string b){
  5.     int ret =0;
  6.     for(int i = 0 ; i<a.length(); i++){
  7.         if(a[i]!=b[i])  ret++;
  8.         if(ret>1)   return ret;
  9.     }  
  10.     return ret;
  11. }
  12. int ladderLength(string beginWord, string endWord, unordered_set<string>& wordList) {
  13.     unordered_map<string,vector<string> > adj;
  14.     vector<string> words;
  15.     for(string s : wordList)    words.push_back(s);
  16.     words.push_back(beginWord);
  17.     words.push_back(endWord);
  18.     set<string> tp;
  19.     for(string s : words)   tp.insert(s);
  20.     words.clear();
  21.     for(string s : tp)  words.push_back(s);
  22.     for(int i = 0 ; i< words.size(); i++)
  23.         for(int j = i+1; j<words.size(); j++)
  24.             if(dist(words[i],words[j])==1){
  25.                 adj[words[i]].push_back(words[j]);
  26.                 adj[words[j]].push_back(words[i]);
  27.             }
  28.     unordered_map<string,int> vis;
  29.     queue<pair<string, int> > q;
  30.     q.push({beginWord,1});
  31.     vis[beginWord]=1;
  32.     while(!q.empty()){
  33.         string cur = q.front().first;
  34.         int dis = q.front().second;
  35.         q.pop();
  36.         if(cur==endWord)  return dis;
  37.         for(string s : adj[cur]){
  38.             if(!vis.count(s)){
  39.                 q.push({s,dis+1});
  40.                 vis[s]=1;
  41.             }
  42.         }
  43.     }
  44.     return 0;
  45. }
  46.  
  47. int main() {
  48. 	unordered_set<string> s = {"hot","dot","dog","lot","log"};
  49. 	cout<<ladderLength("hit","cog",s);
  50. 	return 0;
  51. }
Success #stdin #stdout 0s 3472KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
5
https://ideone.com/u9lH3n
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!