Word Ladder

Leetcode

Problem Statement

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s_1 -> s_2 -> ... -> s_k such that:

• Every adjacent pair of words differs by a single letter.
• Every s_i for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
• s_k == endWord

Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.

Solution

class Solution {
public:
    int getDiff(string a, string b) {
        int diff = 0;
        for (int i = 0; i < max(a.size(), b.size()); i++) {
            if (i < a.size() && i < b.size()) {
                if (a[i] != b[i]) diff++;
            } else {
                diff++;
            }
        }
        return diff;
    }

    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        int n = wordList.size();
        // vector<bool> seen(n, false);
        unordered_set<string> unusedWords;
        for (const auto s: wordList) {
            if (s != beginWord) unusedWords.insert(s);
        }

        vector<string> seq;

        queue<pair<string, int>> q;

        q.push({beginWord, 1});
        while (!q.empty()) {
            auto t = q.front();
            q.pop();
            string a = t.first;
            int stage = t.second;
            // while (seq.size() >= stage) {
            //     seq.pop_back();
            // }
            // seq.push_back({ a });
            vector<string> matchingWords;

            for (auto s: unusedWords) {
                if (getDiff(a, s) == 1) {
                    if (s == endWord) {
                        // for (auto p: seq) {
                        //     cout << p << "\n";
                        // }
                        // cout << s << "\n";
                        return stage + 1;
                    } else {
                        matchingWords.push_back(s);
                    } 
                }
            }

            for (const string s: matchingWords) {
                q.push({s, stage + 1});
                unusedWords.erase(s);
            }
        }

        return 0;
        
    }
};