# BFS C++ solution with adjacency list and queue

• 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;
}

for (int i = 0; i + 1 < adjacencyList.size(); i++) {
for (int j = i + 1; j < adjacencyList.size(); j++) {
if (oneMutationAway(bank[i], bank[j])) {
}
}
}
}

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();

// 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;
}
};
``````

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