127. Word Ladder

https://leetcode.com/problems/word-ladder/

Problem

Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

1. Only one letter can be changed at a time.

2. Each transformed word must exist in the word list.

Note:

• Return 0 if there is no such transformation sequence.

• All words have the same length.

• All words contain only lowercase alphabetic characters.

• You may assume no duplicates in the word list.

• You may assume beginWord and endWord are non-empty and are not the same.

Example 1:

Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

Output: 5

Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Example 2:

Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

Output: 0

Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.

Solution

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string> &wordList) {
        bool found = false;
        int distance = 2;
        stack<string> words, next_words;
        for (int i = 0; i < wordList.size(); ++i) {
            if (wordList[i] != endWord) continue;
            found = true;
            words.push(wordList[i]);
            wordList[i] = wordList.back();
            wordList.pop_back();
            break;
        }
        if (!found) return 0;
        while (!words.empty()) {
            string target = words.top();
            words.pop();
            if (reachable(beginWord, target)) {
                return distance;
            } 

            for (int i = 0; i < wordList.size(); ++i) {
                if (reachable(wordList[i], target)) {
                    next_words.push(wordList[i]);
                    wordList[i] = wordList.back();
                    wordList.pop_back();
                }
            }
            if (words.empty()) {
                words.swap(next_words);
                ++distance;
            }        
        }
        return 0;
    }
    
    inline bool reachable(string &from, string &to) {
        int count = 0;
        for (int i = 0; i < from.size(); ++i) {
            if (from[i] != to[i]) ++count;
            if (count > 1) return false;
        }
        return true;
    }    
};

• #bfs

• #important