Self explaining solution with BFS


  • 0
        bool isNeighbour(string& w1, string& w2) {
            bool res = false;
            for (int i = 0; i < w1.size(); ++i) {
                if (w1[i] != w2[i]) {
                    if (res) return false;
                    res = true;
                }
            }
            return res;
        }
        
        int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
            int n = wordList.size() + 1;
            vector<vector<int> > graph(n, vector<int>(0));
    
            // Create the graph.
            for (int i = 0; i < wordList.size(); ++i) {
                if (isNeighbour(beginWord, wordList[i])) {
                    graph[0].push_back(i + 1);
                    graph[i + 1].push_back(0);
                }
                for (int j = i + 1; j < wordList.size(); ++j) {
                    if (isNeighbour(wordList[i], wordList[j])) {
                        graph[i + 1].push_back(j + 1);
                        graph[j + 1].push_back(i + 1);
                    }
                }
            }
    
            // Debug information:
            // for (int i = 0; i < n; ++i) {
            //    cout << i << " : ";
            //     for (int j = 0; j < graph[i].size(); ++j) {
            //         cout << graph[i][j] << ", ";
            //     }
            //     cout << endl;
            // }
                    
            queue<pair<int, int> > q;
            vector<bool> vis(n, false);
    
            q.push(make_pair(0, 1));
            vis[0] = true;
    
            // BFS
            while (!q.empty()) {
                int v = q.front().first;
                int len = q.front().second;
                q.pop();
                for (auto nb : graph[v]) {
                    if (!vis[nb]) {
                        // End condition.
                        if (wordList[nb - 1] == endWord) return len + 1;
                        vis[nb] = true;
                        q.push(make_pair(nb, len + 1));
                    }
                }
            }
            return 0;
        }
    

Log in to reply
 

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