# Self explaining solution with BFS

• ``````    bool isNeighbour(string& w1, string& w2) {
bool res = false;
for (int i = 0; i < w1.size(); ++i) {
if (w1[i] != w2[i]) {
if (res) return false;
res = true;
}
}
return res;
}

int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
int n = wordList.size() + 1;
vector<vector<int> > graph(n, vector<int>(0));

// Create the graph.
for (int i = 0; i < wordList.size(); ++i) {
if (isNeighbour(beginWord, wordList[i])) {
graph[0].push_back(i + 1);
graph[i + 1].push_back(0);
}
for (int j = i + 1; j < wordList.size(); ++j) {
if (isNeighbour(wordList[i], wordList[j])) {
graph[i + 1].push_back(j + 1);
graph[j + 1].push_back(i + 1);
}
}
}

// Debug information:
// for (int i = 0; i < n; ++i) {
//    cout << i << " : ";
//     for (int j = 0; j < graph[i].size(); ++j) {
//         cout << graph[i][j] << ", ";
//     }
//     cout << endl;
// }

queue<pair<int, int> > q;
vector<bool> vis(n, false);

q.push(make_pair(0, 1));
vis[0] = true;

// BFS
while (!q.empty()) {
int v = q.front().first;
int len = q.front().second;
q.pop();
for (auto nb : graph[v]) {
if (!vis[nb]) {
// End condition.
if (wordList[nb - 1] == endWord) return len + 1;
vis[nb] = true;
q.push(make_pair(nb, len + 1));
}
}
}
return 0;
}
``````

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