Word Ladder

You are given two words - beginWord and endWord. You also have a wordList of size n.
All words are of the same length.

You have to create a transformation sequence from beginWord to endWord that looks like this:
beginWord → str1 → str2 → str3 → … → strk

Adjacent pairs in the sequence differ by a single character, and all strings from str1 to strk lie in wordList.

Also strk = endWord.

Find the minimum number of words in the shortest possible transformation sequence. If such a sequence is not possible return 0.

c++

bool near(string& a, string& b) {
    int i = 0, diff = 0, n = a.length();
    while(i < n and diff <= 1) {
        if(a[i] != b[i]) diff++;
        i++;
    }
    return i == n and diff == 1;
}

int shortestLadderLength(string beginWord, string endWord,
                         vector<string> &wordList) {
    unordered_map<string, vector<string>> adj;
    int n = wordList.size();
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(near(wordList[i], wordList[j])) {
                adj[wordList[i]].push_back(wordList[j]);
                adj[wordList[j]].push_back(wordList[i]);
            }
        }
        if(near(wordList[i], beginWord)) {
            adj[wordList[i]].push_back(beginWord);
            adj[beginWord].push_back(wordList[i]);
        }
        if(near(wordList[i], endWord)) {
            adj[wordList[i]].push_back(endWord);
            adj[endWord].push_back(wordList[i]);
        }
    }
	
	if(near(beginWord, endWord)) {
		return 2;
	}
    
    unordered_set<string> vis{beginWord};
    queue<string> q;
    q.push(beginWord);
    int res = 2;
    
    while(!q.empty()) {
        int sz = q.size();
        while(sz--) {
            auto u = q.front(); q.pop();
            for(auto& v : adj[u]) {
                if(vis.count(v)) continue;
                vis.insert(v);
                q.push(v);
                if(v == endWord) return res;
            }
        }
        res++;
    }
 
    return 0;
}