Definitely not the shortest solution. But I hope the idea is easy to understand. The problem can be reduced to: determine if `start`

is connected to`end`

in a graph, where two nodes are directly connected if they are one mutation apart. I use a vector of adjacency lists here as the data structure. But if the graph is dense enough, a 2D array is a reasonable alternative.

In each iteration of the loop we check if we arrive at the end string. If so, return the number of visited nodes so far. Otherwise, push all the next nodes onto the queue.

```
class Solution {
public:
bool oneMutationAway(string& s1, string& s2) {
int diff = 0;
for (int i = 0; i < 8; i++) {
if (s1[i] != s2[i])
diff++;
if (diff > 1)
return false;
}
return diff == 1;
}
void constructAdjacencyList(vector<list<int>>& adjacencyList, vector<string>& bank) {
for (int i = 0; i + 1 < adjacencyList.size(); i++) {
for (int j = i + 1; j < adjacencyList.size(); j++) {
if (oneMutationAway(bank[i], bank[j])) {
adjacencyList[i].push_back(j);
adjacencyList[j].push_back(i);
}
}
}
}
using node = pair<int, set<int>>;
int minMutation(string start, string end, vector<string>& bank) {
auto it = find(bank.begin(), bank.end(), end);
if (it == bank.end())
return -1;
int endIdx = it - bank.begin(), bankSize = bank.size();
vector<list<int>> adjacencyList(bankSize);
constructAdjacencyList(adjacencyList, bank);
// queue for BFS
queue<node> q;
for (int i = 0; i < bankSize; i++) {
if (oneMutationAway(start, bank[i])) {
set<int> reached;
reached.insert(i);
q.emplace(i, reached);
}
}
while (!q.empty()) {
node curNode = q.front();
q.pop();
int curIdx = curNode.first;
set<int> curReached = curNode.second;
if (curIdx == endIdx)
return curReached.size();
for (int next : adjacencyList[curIdx]) {
// if next is unvisited
if (curReached.find(next) == curReached.end()) {
curReached.insert(next);
q.emplace(next, curReached);
curReached.erase(next);
}
}
}
return -1;
}
};
```