Word Ladder II

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

Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) 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 that beginWord is not a transformed word.

Thoughts

参考https://zxi.mytechroad.com/blog/searching/leetcode-126-word-ladder-ii/

找最短距离用BFS，找具体路径用DFS。先用BFS生成地图childrens，指明从start到end每层的每个点下一步可以遍历哪些点。为了进一步刨除不能遍历的点，交替进行两头的BFS: 每次选择空间少的那个继续遍历下一层，当俩交汇时说明已经遍历到最后一层。再根据地图从start做DFS。或者用map记录节点到终点的距离，DFS时跳过不符合最短距离的点。

Code

/*
 * @lc app=leetcode id=126 lang=cpp
 *
 * [126] Word Ladder II
 */
class Solution {
public:
    unordered_map<string, unordered_set<string>> bfs(unordered_set<string> &words, const string start, const string end) {
        unordered_set<string> q1({start});
        unordered_set<string> q2({end});
        unordered_map<string, unordered_set<string>> childrens;
        bool found = false, backward = false;
        while (!q1.empty() && !q2.empty() && !found) {
            for (const auto &w : q1) words.erase(w);
            for (const auto &w : q2) words.erase(w);
            unordered_set<string> nq;
            if (q1.size() > q2.size()) {
                swap(q1, q2);
                backward = !backward;
            }
            for (const auto &t : q1) {
                auto w = t;
                for (int i = 0; i < t.size(); ++i) {
                    const char ch = w[i];
                    for (char c = 'a'; c <= 'z'; ++c) {
                        w[i] = c;
                        const auto *parent = &t;
                        const auto *child = &w;
                        if (backward) swap(parent, child); 
                        if (q2.count(w)) {
                            found = true;
                            childrens[*parent].insert(*child); 
                        } else if (words.count(w)) {
                            childrens[*parent].insert(*child);
                            nq.insert(w);
                        }
                    }
                    w[i] = ch;
                }
            }
            swap(q1, nq);
        }
        return childrens;
    }

    void dfs(unordered_map<string, unordered_set<string>> &childrens, const string end, const string cur, vector<string> &path, vector<vector<string>> &res) {
        if (cur == end) {
            res.push_back(path);
            return;
        }
        for (const auto &c : childrens[cur]) {
            path.push_back(c);
            dfs(childrens, end, c, path, res);
            path.pop_back();
        }
    }

    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> words(wordList.begin(), wordList.end());
        if (!words.count(endWord)) return {};
        auto childrens = bfs(words, beginWord, endWord);
        vector<string> path({beginWord});
        vector<vector<string>> res;
        dfs(childrens, endWord, beginWord, path, res);
        return res;
    }
};

Analysis

Errors: 1. 每次动态计算neighbors很花时间, TLE 时间复杂度O(N), N为dict长度. 因为所生成的递归树每个节点是一个word, 最多有O(N)个节点.

Ver.2

还可以只用BFS. 这时 BFS存的就不再是单个的node, 而是一条path. 注意题意要求返回最短的路径, 也就是说所有在当前层和之前层出现过的节点都无需在未来层出现, 否则相当于在访问过某点后又重新引入该点(无论是否在同一条path), 无谓的增加了长度. 比如当前访问了 [a, c] a的下一个点是c, 那[a, c]和c之后将访问一样的点, 只是前者无意义的引入了a.

class Solution {
    // Find all next level nodes.    
    private ArrayList<String> getNeighbors(String node, Set<String> dict) {
        ArrayList<String> res = new ArrayList<String>();
        char chs[] = node.toCharArray();

        for (char ch ='a'; ch <= 'z'; ch++) {
            for (int i = 0; i < chs.length; i++) {
                if (chs[i] == ch) continue;
                    char old_ch = chs[i];
                    chs[i] = ch;
                if (dict.contains(String.valueOf(chs))) {
                    res.add(String.valueOf(chs));
                }
                chs[i] = old_ch;
            }
        }
        return res;
    }

    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        List<List<String>> res = new ArrayList<>();
        Set<String> dict = new HashSet<String>(wordList);
        if (!dict.contains(endWord)) {
            return res;
        }
        dict.add(beginWord);
        Queue<List<String>> queue = new LinkedList<>();
        Map<String, List<String>> nodeNeighbors = new HashMap<>();

        List<String> spath = new ArrayList<>();
        spath.add(beginWord);
        queue.add(spath);
        boolean found = false;
        Set<String> wordsPerLevel = new HashSet<String>();
        while (!queue.isEmpty()) {
            if (found) {
                break;
            }
            int size = queue.size();
            wordsPerLevel.clear();
            List<List<String>> list = (List)queue;
            for (int i = 0; i < size; i++) {
                List<String> path = list.get(i);
                wordsPerLevel.add(path.get(path.size() - 1));
            }
            dict.removeAll(wordsPerLevel);

            for (int i = 0; i < size; i++) {
                List<String> path = queue.poll();
                String str = path.get(path.size() - 1);
                if (str.equals(endWord)) {
                    res.add(path);
                    found = true;
                    continue;
                }
                for (String neighbor : getNeighbors(str, dict)) {
                    List<String> newPath = new ArrayList<>(path);
                    newPath.add(neighbor);
                    queue.add(newPath);
                }
            }
        }

        return res;
    }
}

Analysis

时间复杂度O(N), 最差N个word每个都访问遍