Word Ladder II

描述

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

  • Only one letter can be changed at a time
  • Each intermediate word must exist in the dictionary
    For example, Given:
  1. start = "hit"
  2. end = "cog"
  3. dict = ["hot","dot","dog","lot","log"]

Return

  1. [
  2.     ["hit","hot","dot","dog","cog"],
  3.     ["hit","hot","lot","log","cog"]
  4. ]

Note:

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

    分析

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

求一条路径和求所有路径有很大的不同，求一条路径，每个状态节点只需要记录一个前驱即可；求所有路径时，有的状态节点可能有多个父节点，即要记录多个前驱。

如果当前路径长度已经超过当前最短路径长度，可以中止对该路径的处理，因为我们要找的是最短路径。

单队列

  1. // Word Ladder II
  2. // 时间复杂度O(n)，空间复杂度O(n)
  3. class Solution {
  4. public:
  5.     vector<vector<string> > findLadders(const string& start,
  6.         const string& end, const unordered_set<string> &dict) {
  7.         queue<string> q;
  8.         unordered_map<string, int> visited; // 判重
  9.         unordered_map<string, vector<string> > father; // DAG
  11.         auto state_is_valid = [&](const string& s) {
  12.             return dict.find(s) != dict.end() || s == end;
  13.         };
  14.         auto state_is_target = [&](const string &s) {return s == end; };
  15.         auto state_extend = [&](const string &s) {
  16.             unordered_set<string> result;
  17.             const int new_depth = visited[s] + 1;
  19.             for (size_t i = 0; i < s.size(); ++i) {
  20.                 string new_state = s;
  21.                 for (char c = 'a'; c <= 'z'; c++) {
  22.                     // 防止同字母替换
  23.                     if (c == new_state[i]) continue;
  25.                     swap(c, new_state[i]);
  27.                     if (state_is_valid(new_state)) {
  28.                         auto visited_iter = visited.find(new_state);
  30.                         if (visited_iter != visited.end()) {
  31.                             const int depth = visited_iter->second;
  32.                             if (depth < new_depth) {
  33.                                 // do nothing
  34.                             }
  35.                             else if (depth == new_depth) {
  36.                                 result.insert(new_state);
  37.                             }
  38.                             else { // not possible
  39.                                 throw std::logic_error("not possible to get here");
  40.                             }
  41.                         }
  42.                         else {
  43.                             result.insert(new_state);
  44.                         }
  45.                     }
  46.                     swap(c, new_state[i]); // 恢复该单词
  47.                 }
  48.             }
  50.             return result;
  51.         };
  53.         vector<vector<string>> result;
  54.         q.push(start);
  55.         visited[start] = 0;
  56.         while (!q.empty()) {
  57.             // 千万不能用 const auto&，pop() 会删除元素，
  58.             // 引用就变成了悬空引用
  59.             const auto state = q.front();
  60.             q.pop();
  62.             // 如果当前路径长度已经超过当前最短路径长度，
  63.             // 可以中止对该路径的处理，因为我们要找的是最短路径
  64.             if (!result.empty() && visited[state] + 1 > result[0].size()) break;
  66.             if (state_is_target(state)) {
  67.                 vector<string> path;
  68.                 gen_path(father, start, state, path, result);
  69.                 continue;
  70.             }
  71.             // 必须挪到下面，比如同一层A和B两个节点均指向了目标节点，
  72.             // 那么目标节点就会在q中出现两次，输出路径就会翻倍
  73.             // visited.insert(state);
  75.             // 扩展节点
  76.             const auto& new_states = state_extend(state);
  77.             for (const auto& new_state : new_states) {
  78.                 if (visited.find(new_state) == visited.end()) {
  79.                     q.push(new_state);
  80.                     visited[new_state] = visited[state] + 1;
  81.                 }
  82.                 father[new_state].push_back(state);
  83.             }
  84.         }
  86.         return result;
  87.     }
  88. private:
  89.     void gen_path(unordered_map<string, vector<string> > &father,
  90.         const string &start, const string &state, vector<string> &path,
  91.         vector<vector<string> > &result) {
  92.         path.push_back(state);
  93.         if (state == start) {
  94.             if (!result.empty()) {
  95.                 if (path.size() < result[0].size()) {
  96.                     result.clear();
  97.                 }
  98.                 else if (path.size() == result[0].size()) {
  99.                     // do nothing
  100.                 }
  101.                 else { // not possible
  102.                     throw std::logic_error("not possible to get here ");
  103.                 }
  104.             }
  105.             result.push_back(path);
  106.             reverse(result.back().begin(), result.back().end());
  107.         }
  108.         else {
  109.             for (const auto& f : father[state]) {
  110.                 gen_path(father, start, f, path, result);
  111.             }
  112.         }
  113.         path.pop_back();
  114.     }
  115. };

双队列

  1. // Word Ladder II
  2. // 时间复杂度O(n)，空间复杂度O(n)
  3. class Solution {
  4. public:
  5.     vector<vector<string> > findLadders(const string& start,
  6.             const string& end, const unordered_set<string> &dict) {
  7.         // 当前层，下一层，用unordered_set是为了去重，例如两个父节点指向
  8.         // 同一个子节点，如果用vector, 子节点就会在next里出现两次，其实此
  9.         // 时 father 已经记录了两个父节点，next里重复出现两次是没必要的
  10.         unordered_set<string> current, next;
  11.         unordered_set<string> visited; // 判重
  12.         unordered_map<string, vector<string> > father; // DAG
  14.         int level = -1;  // 层次
  16.         auto state_is_valid = [&](const string& s) {
  17.             return dict.find(s) != dict.end() || s == end;
  18.         };
  19.         auto state_is_target = [&](const string &s) {return s == end;};
  20.         auto state_extend = [&](const string &s) {
  21.             unordered_set<string> result;
  23.             for (size_t i = 0; i < s.size(); ++i) {
  24.                 string new_word(s);
  25.                 for (char c = 'a'; c <= 'z'; c++) {
  26.                     // 防止同字母替换
  27.                     if (c == new_word[i]) continue;
  29.                     swap(c, new_word[i]);
  31.                     if (state_is_valid(new_word) &&
  32.                             visited.find(new_word) == visited.end()) {
  33.                         result.insert(new_word);
  34.                     }
  35.                     swap(c, new_word[i]); // 恢复该单词
  36.                 }
  37.             }
  39.             return result;
  40.         };
  42.         vector<vector<string> > result;
  43.         current.insert(start);
  44.         while (!current.empty()) {
  45.             ++ level;
  46.             // 如果当前路径长度已经超过当前最短路径长度，可以中止对该路径的
  47.             // 处理，因为我们要找的是最短路径
  48.             if (!result.empty() && level+1 > result[0].size()) break;
  50.             // 1. 延迟加入visited, 这样才能允许两个父节点指向同一个子节点
  51.             // 2. 一股脑current 全部加入visited, 是防止本层前一个节点扩展
  52.             // 节点时，指向了本层后面尚未处理的节点，这条路径必然不是最短的
  53.             for (const auto& state : current)
  54.                 visited.insert(state);
  55.             for (const auto& state : current) {
  56.                 if (state_is_target(state)) {
  57.                     vector<string> path;
  58.                     gen_path(father, path, start, state, result);
  59.                     continue;
  60.                 }
  62.                 const auto new_states = state_extend(state);
  63.                 for (const auto& new_state : new_states) {
  64.                     next.insert(new_state);
  65.                     father[new_state].push_back(state);
  66.                 }
  67.             }
  69.             current.clear();
  70.             swap(current, next);
  71.         }
  73.         return result;
  74.     }
  75. private:
  76.     void gen_path(unordered_map<string, vector<string> > &father,
  77.             vector<string> &path, const string &start, const string &word,
  78.             vector<vector<string> > &result) {
  79.         path.push_back(word);
  80.         if (word == start) {
  81.             if (!result.empty()) {
  82.                 if (path.size() < result[0].size()) {
  83.                     result.clear();
  84.                     result.push_back(path);
  85.                 } else if(path.size() == result[0].size()) {
  86.                     result.push_back(path);
  87.                 } else {
  88.                     // not possible
  89.                     throw std::logic_error("not possible to get here");
  90.                 }
  91.             } else {
  92.                 result.push_back(path);
  93.             }
  94.             reverse(result.back().begin(), result.back().end());
  95.         } else {
  96.             for (const auto& f : father[word]) {
  97.                 gen_path(father, path, start, f, result);
  98.             }
  99.         }
  100.         path.pop_back();
  101.     }
  102. };

图的广搜

前面的解法，在状态扩展的时候，每次都是从'a'到'z'全部枚举一遍，重复计算，比较浪费，其实当给定字典dict后，单词与单词之间的路径就固定下来了，本质上单词与单词之间构成了一个无向图。如果事先把这个图构建出来，那么状态扩展就会大大加快。

  1. // Word Ladder II
  2. // 时间复杂度O(n)，空间复杂度O(n)
  3. class Solution {
  4. public:
  5.     vector<vector<string> > findLadders(const string& start,
  6.         const string& end, const unordered_set<string> &dict) {
  7.         queue<string> q;
  8.         unordered_map<string, int> visited; // 判重
  9.         unordered_map<string, vector<string> > father; // DAG
  10.         // only used by state_extend()
  11.         const unordered_map<string, unordered_set<string> >& g = build_graph(dict);
  13.         auto state_is_valid = [&](const string& s) {
  14.             return dict.find(s) != dict.end() || s == end;
  15.         };
  16.         auto state_is_target = [&](const string &s) {return s == end; };
  17.         auto state_extend = [&](const string &s) {
  18.             vector<string> result;
  19.             const int new_depth = visited[s] + 1;
  20.             auto iter = g.find(s);
  21.             if (iter == g.end()) return result;
  22.             const auto& list = iter->second;
  24.             for (const auto& new_state : list) {
  25.                 if (state_is_valid(new_state)) {
  26.                     auto visited_iter = visited.find(new_state);
  27.                     if (visited_iter != visited.end()) {
  28.                         const int depth = visited_iter->second;
  29.                         if (depth < new_depth) {
  30.                             // do nothing
  31.                         }
  32.                         else if (depth == new_depth) {
  33.                             result.push_back(new_state);
  34.                         } else { // not possible
  35.                             throw std::logic_error("not possible to get here");
  36.                         }
  37.                     }
  38.                     else {
  39.                         result.push_back(new_state);
  40.                     }
  41.                 }
  42.             }
  44.             return result;
  45.         };
  47.         vector<vector<string>> result;
  48.         q.push(start);
  49.         visited[start] = 0;
  50.         while (!q.empty()) {
  51.             // 千万不能用 const auto&，pop() 会删除元素，
  52.             // 引用就变成了悬空引用
  53.             const auto state = q.front();
  54.             q.pop();
  56.             // 如果当前路径长度已经超过当前最短路径长度，
  57.             // 可以中止对该路径的处理，因为我们要找的是最短路径
  58.             if (!result.empty() && visited[state] + 1 > result[0].size()) break;
  60.             if (state_is_target(state)) {
  61.                 vector<string> path;
  62.                 gen_path(father, start, state, path, result);
  63.                 continue;
  64.             }
  65.             // 必须挪到下面，比如同一层A和B两个节点均指向了目标节点，
  66.             // 那么目标节点就会在q中出现两次，输出路径就会翻倍
  67.             // visited.insert(state);
  69.             // 扩展节点
  70.             const auto& new_states = state_extend(state);
  71.             for (const auto& new_state : new_states) {
  72.                 if (visited.find(new_state) == visited.end()) {
  73.                     q.push(new_state);
  74.                     visited[new_state] = visited[state] + 1;
  75.                 }
  76.                 father[new_state].push_back(state);
  77.             }
  78.         }
  80.         return result;
  81.     }
  82. private:
  83.     void gen_path(unordered_map<string, vector<string> > &father,
  84.         const string &start, const string &state, vector<string> &path,
  85.         vector<vector<string> > &result) {
  86.         path.push_back(state);
  87.         if (state == start) {
  88.             if (!result.empty()) {
  89.                 if (path.size() < result[0].size()) {
  90.                     result.clear();
  91.                 }
  92.                 else if (path.size() == result[0].size()) {
  93.                     // do nothing
  94.                 }
  95.                 else { // not possible
  96.                     throw std::logic_error("not possible to get here ");
  97.                 }
  98.             }
  99.             result.push_back(path);
  100.             reverse(result.back().begin(), result.back().end());
  101.         }
  102.         else {
  103.             for (const auto& f : father[state]) {
  104.                 gen_path(father, start, f, path, result);
  105.             }
  106.         }
  107.         path.pop_back();
  108.     }
  109.     unordered_map<string, unordered_set<string> > build_graph(
  110.         const unordered_set<string>& dict) {
  111.         unordered_map<string, unordered_set<string> > adjacency_list;
  113.         for (const auto& word : dict) {
  114.             for (size_t i = 0; i < word.size(); ++i) {
  115.                 string new_word(word);
  116.                 for (char c = 'a'; c <= 'z'; c++) {
  117.                     // 防止同字母替换
  118.                     if (c == new_word[i]) continue;
  120.                     swap(c, new_word[i]);
  122.                     if ((dict.find(new_word) != dict.end())) {
  123.                         auto iter = adjacency_list.find(word);
  124.                         if (iter != adjacency_list.end()) {
  125.                             iter->second.insert(new_word);
  126.                         }
  127.                         else {
  128.                             adjacency_list.insert(pair<string,
  129.                                 unordered_set<string >> (word, unordered_set<string>()));
  130.                             adjacency_list[word].insert(new_word);
  131.                         }
  132.                     }
  133.                     swap(c, new_word[i]); // 恢复该单词
  134.                 }
  135.             }
  136.         }
  137.         return adjacency_list;
  138.     }
  139. };

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/cpp/bfs/word-ladder-ii.html