Word Ladder I

• Time : O(v^2 + v + e)
• Space : O(v + e)

c++

bool change(string& A, string& B) {
    int diff = 0;
    for(int i = 0; i < A.length() and diff < 2; i++) diff += (A[i] != B[i]);
    return diff == 1;
}

int Solution::solve(string A, string B, vector<string> &C) {
    unordered_map<string, vector<string>> adj;
    for(int i = 0; i < C.size(); i++) {
        for(int j = i + 1; j < C.size(); j++) {
            if(change(C[i],C[j])) {
                adj[C[i]].push_back(C[j]);
                adj[C[j]].push_back(C[i]);
            }
        }
        if(change(C[i],A)) {
            adj[C[i]].push_back(A);
            adj[A].push_back(C[i]);
        }
        if(change(C[i],B)) {
            adj[C[i]].push_back(B);
            adj[B].push_back(C[i]);
        }
    }
    int res = 1;
    queue<string> Q;
    Q.push(A);
    unordered_set<string> us;
    us.insert(A);
    while(!Q.empty()) {
        int sz = Q.size();
        while(sz--) {
            auto u = Q.front(); Q.pop();
            for(auto& v : adj[u]) {
                if(us.count(v)) continue;
                if(v == B) return res + 1;
                us.insert(v);
                Q.push(v);
            }
        }
        res++;
    }
    
    return 0;
}