BFS C++ solution with adjacency list and queue


  • 0

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

Log in to reply
 

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