首页 > 搜索 > BFS搜索 > LeetCode-Word Ladder II[BFS]
2014
11-18

LeetCode-Word Ladder II[BFS]

Word Ladder II

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:

  1. Only one letter can be changed at a time
  2. Each intermediate word must exist in the dictionary

For example,

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

Return

  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]

Note:

  • All words have the same length.
  • All words contain only lowercase alphabetic characters.

标签: Array Backtracking Breadth-first Search String
分析

跟 Word Ladder比,这题是求路径本身,不是路径长度,也是BFS,略微麻烦点。

这题跟普通的广搜有很大的不同,就是要输出所有路径,因此在记录前驱和判重地方与普通广搜略有不同。

代码1

//LeetCode, Word Ladder II
// 时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    vector<vector<string> > findLadders(string start, string end,
            const unordered_set<string> &dict) {
        unordered_set<string> current, next;  // 当前层,下一层,用集合是为了去重
        unordered_set<string> visited; // 判重
        unordered_map<string, vector<string> > father; // 树

        bool found = false;

        auto state_is_target = [&](const string &s) {return s == end;};
        auto state_extend = [&](const string &s) {
            unordered_set<string> result;

            for (size_t i = 0; i < s.size(); ++i) {
                string new_word(s);
                for (char c = 'a'; c <= 'z'; c++) {
                    if (c == new_word[i]) continue;

                    swap(c, new_word[i]);

                    if ((dict.count(new_word) > 0|| new_word == end) &&
                             !visited.count(new_word)) {
                        result.insert(new_word);
                    }
                    swap(c, new_word[i]); // 恢复该单词
                }
            }

            return result;
        };

        current.insert(start);
        while (!current.empty() && !found) {
            // 先将本层全部置为已访问,防止同层之间互相指向
            for (const auto& word : current)
                visited.insert(word);
            for (const auto& word : current) {
                const auto new_states = state_extend(word);
                for (const auto &state : new_states) {
                    if (state_is_target(state)) found = true;
                    next.insert(state);
                    father[state].push_back(word);
                    // visited.insert(state); // 移动到最上面了
                }
            }

            current.clear();
            swap(current, next);
        }
        vector<vector<string> > result;
        if (found) {
            vector<string> path;
            gen_path(father, path, start, end, result);
        }
        return result;
    }
private:
    void gen_path(unordered_map<string, vector<string> > &father,
            vector<string> &path, const string &start, const string &word,
            vector<vector<string> > &result) {
        path.push_back(word);
        if (word == start) {
            result.push_back(path);
            reverse(result.back().begin(), result.back().end());
        } else {
            for (const auto& f : father[word]) {
                gen_path(father, path, start, f, result);
            }
        }
        path.pop_back();
    }
};

相关题目
Word Ladder


  1. 第二块代码if(it != mp.end())应改为if(it != mp.end() && (i+1)!=(it->second +1));因为第二种解法如果数组有重复元素 就不正确

  2. Often We don’t set up on weblogs, but I would like to condition that this established up really forced me individually to do this! considerably outstanding publish