Word Ladder I

Given two distinct words startWord and targetWord, and a list denoting wordList of unique words of equal lengths. Find the length of the shortest transformation sequence from startWord to targetWord.

Keep the following conditions in mind:

• A word can only consist of lowercase characters.
• Only one letter can be changed in each transformation.
• Each transformed word must exist in the wordList including the targetWord.
• startWord may or may not be part of the wordList.

The second part of this problem can be found here.

• Time : O(|wordList| |wordList| n + v + e)
• Space : O(|wordList| + e)

c++

class Solution {
    bool connected(string a, string b) {
        int diff = 0;
        for(int i = 0; i < a.length() and diff < 2; i++) {
            if(a[i] != b[i]) diff++;
        }
        return diff == 1;
    }
public:
    int wordLadderLength(string startWord, string targetWord, vector<string>& wordList) {
        if(startWord == targetWord) return 1;
        unordered_map<string, int> mp;
        mp[startWord] = 1;
        int no = 2;
        for(auto& word : wordList) {
            if(mp.count(word)) continue;
            mp[word] = no++;
        }
        if(!mp.count(targetWord)) return 0;
        int goal = mp[targetWord];
        vector<vector<int>> adj(no + 1);
        
        for(auto i = begin(mp); i != end(mp); i++) {
            for(auto j = next(i); j != end(mp); j++) {
                if(connected(i->first, j->first)) {
                    adj[i->second].push_back(j->second);
                    adj[j->second].push_back(i->second);
                }
            }
        }
        
        vector<int> vis(no + 1, 0);
        queue<int> q;
        q.push(1);
        vis[1] = 1;
        while(!q.empty()) {
            auto u = q.front(); q.pop();
            for(auto& v : adj[u]) {
                if(v == goal) return vis[u] + 1;
                if(vis[v]) continue;
                vis[v] = vis[u] + 1;
                q.push(v);
            }
        }
        
        return 0;
    }
};