Simple BFS solution

• ``````using namespace std;

#define PI acos(-1)
#define sqr(x) ((x) * (x))
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define ALL(c) (c).begin(), (c).end()
#define SIZE(c) (int)(c).size()
#define REP(i, a, b) for (int i = int(a); i <= int(b); i++)
#define REPD(i, a, b) for (int i = int(a); i >= int(b); i--)

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<double,double> dd;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<string> vs;
typedef map<int,int> mii;
typedef map<string, int> msi;
typedef set<int> si;

const int INF=1 << 28;

class Solution {
public:
int ladderLength(string start, string end, unordered_set<string> &dict) {
int n = SIZE(dict) + 2, v = 0, wl = start.length(), dist[n];
bool disc[n];
msi h;
REP(i, 0, n-1) { dist[i]=INF; disc[i]=false; }
queue<string> q;

h[start]=v++;
for (unordered_set<string>::iterator it = dict.begin(); it != dict.end(); ++it) {
if(*it != start) {
h[*it]=v++;
}
}
h[end]=v;

q.push(start);
dist[h[start]]=1; //path length is vertex count along path, not edges
disc[h[start]]=true;
string u;
char buf[wl+1];

while(!q.empty()) {
u=q.front(); q.pop();

REP(i, 0, wl-1) {
REP(j, 0, 25) {
strcpy(buf, u.c_str());
buf[i]='a'+j;
string y(buf);

if(h.find(y) != h.end() && y != start) {
int x=h[y];
if(!disc[x]) {
if(y == end) {
dist[x] = min(dist[x], dist[h[u]]+1);
}else {
q.push(y);
disc[x]=true;
dist[x]=dist[h[u]]+1;
}
}
}
}
}
}

if(dist[h[end]] == INF) { return 0; }
else { return dist[h[end]]; }
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.