word_ladder.cpp

#include <cerrno>
#include <cstring>  // for strerror
#include <cctype>   // for tolower
#include <fstream>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <sstream>
#include <vector>

using namespace std;

/*
 * You can define either WORDS_FILE -- file with words, one per line,
 * or WORDS -- '\n' separated list of words.
 *
 * If you are on UNIX-like system, there is a default words file "/usr/share/dict/words".
 */

#define WORDS_FILE "/usr/share/dict/words"
// #define WORDS "dog\ncog\ncag\ncat"

int main(int argc, char **argv) {
    if (argc != 3) {
        cerr << "Usage: " << argv[0] << " WORD1 WORD2\n";
        exit(1);
    }
    string word1(argv[1]), word2(argv[2]);

    if (word1.size() != word2.size()) {
        cerr << "Words should be the same length\n";
        exit(1);
    }

#if defined(WORDS_FILE)
    ifstream wordsin(WORDS_FILE, ios::in);
    if (!wordsin) {
        cerr << "Cannot open " WORDS_FILE ": " << strerror(errno) << '\n';
        exit(1);
    }
#elif defined(WORDS)
    stringstream wordsin(WORDS);
#else
    #error "Define either WORDS or WORDS_FILE"
#endif

    set<string> words;
    string word;
    while (getline(wordsin, word)) {
        if (word.size() == word1.size()) {
            for (char &c : word)
                c = tolower(c);
            words.insert(word);
        }
    }
    for (char &c : word1)
        c = tolower(c);
    for (char &c : word2)
        c = tolower(c);
    words.insert(word1);
    words.insert(word2);

    map<string, vector<string>> graph;
    for (const string &s1 : words) {
        for (const string &s2 : words) {
            int diff = 0;
            for (size_t i = 0; i < word1.size(); ++i)
                if (s1[i] != s2[i])
                    ++diff;
            if (diff == 1) {
                graph[s1].push_back(s2);
                graph[s2].push_back(s1);
            }
        }
    }

    queue<string> q;
    map<string, string> used;
    bool ans = false;
    q.push(word2);
    used[word2] = "";
    while (!q.empty()) {
        string cur = q.front();
        q.pop();
        if (cur == word1) {
            ans = true;
            break;
        }
        for (string &to : graph[cur]) {
            if (!used.count(to)) {
                used[to] = cur;
                q.push(to);
            }
        }
    }

    if (ans) {
        string cur = word1;
        while (cur != "") {
            cout << cur << '\n';
            cur = used[cur];
        }
    } else {
        cout << "Could not find a word ladder\n";
    }

    return 0;
}