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. public class Solution {
  4.     public List<List<String>> findLadders(String beginWord, String endWord,
  5.                                           Set<String> wordList) {
  6.         Queue<String> q = new LinkedList<>();
  7.         HashMap<String, Integer> visited = new HashMap<>(); // 判重
  8.         HashMap<String, ArrayList<String>> father = new HashMap<>(); // DAG
  10.         final Function<String, Boolean> stateIsValid = (String s) ->
  11.                 wordList.contains(s) || s.equals(endWord);
  12.         final Function<String, Boolean> stateIsTarget = (String s) ->
  13.                 s.equals(endWord);
  15.         final Function<String, HashSet<String> > stateExtend = (String s) -> {
  16.             HashSet<String> result = new HashSet<>();
  18.             char[] array = s.toCharArray();
  19.             for (int i = 0; i < array.length; ++i) {
  20.                 final char old = array[i];
  21.                 for (char c = 'a'; c <= 'z'; c++) {
  22.                     // 防止同字母替换
  23.                     if (c == array[i]) continue;
  25.                     array[i] = c;
  26.                     String newState = new String(array);
  27.                     final int newDepth = visited.get(s) + 1;
  29.                     if (stateIsValid.apply(newState)) {
  30.                         if (visited.containsKey(newState)) {
  31.                             final int depth = visited.get(newState);
  32.                             if (depth < newDepth) {
  33.                                 // do nothing
  34.                             } else if (depth == newDepth) {
  35.                                 result.add(newState);
  36.                             } else {
  37.                                 throw new IllegalStateException("not possible to get here");
  38.                             }
  40.                         } else {
  41.                             result.add(newState);
  42.                         }
  43.                     }
  44.                     array[i] = old; // 恢复该单词
  45.                 }
  46.             }
  48.             return result;
  49.         };
  51.         List<List<String>> result = new ArrayList<>();
  52.         q.offer(beginWord);
  53.         visited.put(beginWord, 0);
  54.         while (!q.isEmpty()) {
  55.             String state = q.poll();
  57.             // 如果当前路径长度已经超过当前最短路径长度，
  58.             // 可以中止对该路径的处理，因为我们要找的是最短路径
  59.             if (!result.isEmpty() && (visited.get(state) + 1) > result.get(0).size()) break;
  61.             if (stateIsTarget.apply(state)) {
  62.                 ArrayList<String> path = new ArrayList<>();
  63.                 genPath(father, beginWord, state, path, result);
  64.                 continue;
  65.             }
  66.             // 必须挪到下面，比如同一层A和B两个节点均指向了目标节点，
  67.             // 那么目标节点就会在q中出现两次，输出路径就会翻倍
  68.             // visited.insert(state);
  70.             // 扩展节点
  71.             HashSet<String> newStates = stateExtend.apply(state);
  72.             for (String newState : newStates) {
  73.                 if (!visited.containsKey(newState)) {
  74.                     q.offer(newState);
  75.                     visited.put(newState, visited.get(state)+1);
  76.                 }
  77.                 ArrayList<String> parents = father.getOrDefault(newState, new ArrayList<>());
  78.                 parents.add(state);
  79.                 father.put(newState, parents);
  80.             }
  81.         }
  82.         return result;
  83.     }
  84.     private static void genPath(HashMap<String, ArrayList<String>> father,
  85.                                 String start, String state, List<String> path,
  86.                                 List<List<String>> result) {
  87.         path.add(state);
  88.         if (state.equals(start)) {
  89.             if (!result.isEmpty()) {
  90.                 if (path.size() < result.get(0).size()) {
  91.                     result.clear();
  92.                 } else if (path.size() == result.get(0).size()) {
  93.                     // do nothing
  94.                 } else {
  95.                     throw new IllegalStateException("not possible to get here");
  96.                 }
  97.             }
  98.             ArrayList<String> tmp = new ArrayList<>(path);
  99.             Collections.reverse(tmp);
  100.             result.add(tmp);
  101.         } else {
  102.             for (String f : father.get(state)) {
  103.                 genPath(father, start, f, path, result);
  104.             }
  105.         }
  106.         path.remove(path.size() - 1);
  107.     }
  108. }

双队列

  1. // Word Ladder II
  2. // 时间复杂度O(n)，空间复杂度O(n)
  3. public class Solution {
  4.     public List<List<String>> findLadders(String beginWord, String endWord,
  5.                                           Set<String> wordList) {
  6.         // 当前层，下一层，用unordered_set是为了去重，例如两个父节点指向
  7.         // 同一个子节点，如果用vector, 子节点就会在next里出现两次，其实此
  8.         // 时 father 已经记录了两个父节点，next里重复出现两次是没必要的
  9.         HashSet<String> current = new HashSet<>();
  10.         HashSet<String> next = new HashSet<>();
  11.         HashSet<String> visited = new HashSet<>(); // 判重
  12.         HashMap<String, ArrayList<String>> father = new HashMap<>(); // DAG
  13.         int level = -1; // 层次
  15.         final Function<String, Boolean> stateIsValid = (String s) ->
  16.                 wordList.contains(s) || s.equals(endWord);
  17.         final Function<String, Boolean> stateIsTarget = (String s) ->
  18.                 s.equals(endWord);
  20.         final Function<String, HashSet<String> > stateExtend = (String s) -> {
  21.             HashSet<String> result = new HashSet<>();
  23.             char[] array = s.toCharArray();
  24.             for (int i = 0; i < array.length; ++i) {
  25.                 final char old = array[i];
  26.                 for (char c = 'a'; c <= 'z'; c++) {
  27.                     // 防止同字母替换
  28.                     if (c == array[i]) continue;
  30.                     array[i] = c;
  31.                     String newState = new String(array);
  33.                     if (stateIsValid.apply(newState) &&
  34.                             !visited.contains(newState)) {
  35.                         result.add(newState);
  36.                     }
  37.                     array[i] = old; // 恢复该单词
  38.                 }
  39.             }
  41.             return result;
  42.         };
  44.         List<List<String>> result = new ArrayList<>();
  45.         current.add(beginWord);
  46.         while (!current.isEmpty()) {
  47.             ++ level;
  48.             // 如果当前路径长度已经超过当前最短路径长度，
  49.             // 可以中止对该路径的处理，因为我们要找的是最短路径
  50.             if (!result.isEmpty() && level + 1 > result.get(0).size()) break;
  52.             // 1. 延迟加入visited, 这样才能允许两个父节点指向同一个子节点
  53.             // 2. 一股脑current 全部加入visited, 是防止本层前一个节点扩展
  54.             // 节点时，指向了本层后面尚未处理的节点，这条路径必然不是最短的
  55.             for (String state : current)
  56.                 visited.add(state);
  58.             for (String state : current) {
  59.                 if (stateIsTarget.apply(state)) {
  60.                     ArrayList<String> path = new ArrayList<>();
  61.                     genPath(father, beginWord, state, path, result);
  62.                     continue;
  63.                 }
  64.                 // 扩展节点
  65.                 HashSet<String> newStates = stateExtend.apply(state);
  66.                 for (String newState : newStates) {
  67.                     next.add(newState);
  68.                     ArrayList<String> parents = father.getOrDefault(newState, new ArrayList<>());
  69.                     parents.add(state);
  70.                     father.put(newState, parents);
  71.                 }
  72.             }
  73.             current.clear();
  74.             // swap
  75.             HashSet<String> tmp = current;
  76.             current = next;
  77.             next = tmp;
  79.         }
  80.         return result;
  81.     }
  82.     private static void genPath(HashMap<String, ArrayList<String>> father,
  83.                                 String start, String state, List<String> path,
  84.                                 List<List<String>> result) {
  85.         path.add(state);
  86.         if (state.equals(start)) {
  87.             if (!result.isEmpty()) {
  88.                 if (path.size() < result.get(0).size()) {
  89.                     result.clear();
  90.                 } else if (path.size() == result.get(0).size()) {
  91.                     // do nothing
  92.                 } else {
  93.                     throw new IllegalStateException("not possible to get here");
  94.                 }
  95.             }
  96.             ArrayList<String> tmp = new ArrayList<>(path);
  97.             Collections.reverse(tmp);
  98.             result.add(tmp);
  99.         } else {
  100.             for (String f : father.get(state)) {
  101.                 genPath(father, start, f, path, result);
  102.             }
  103.         }
  104.         path.remove(path.size() - 1);
  105.     }
  106. }

图的广搜

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

  1. import java.util.*;
  2. import java.util.function.Predicate;
  3. import java.util.function.Function;
  5. // Word Ladder II
  6. // 时间复杂度O(n)，空间复杂度O(n)
  7. public class Solution {
  8.     public List<List<String>> findLadders(String beginWord, String endWord,
  9.                                           Set<String> wordList) {
  10.         Queue<String> q = new LinkedList<>();
  11.         HashMap<String, Integer> visited = new HashMap<>(); // 判重
  12.         HashMap<String, ArrayList<String>> father = new HashMap<>(); // DAG
  13.         // only used by stateExtend()
  14.         final HashMap<String, HashSet<String>> g = buildGraph(wordList);
  16.         final Function<String, Boolean> stateIsValid = (String s) ->
  17.                 wordList.contains(s) || s.equals(endWord);
  18.         final Function<String, Boolean> stateIsTarget = (String s) ->
  19.                 s.equals(endWord);
  21.         final Function<String, List<String> > stateExtend = (String s) -> {
  22.             List<String> result = new ArrayList<>();
  23.             final int newDepth = visited.get(s) + 1;
  24.             HashSet<String> list = g.get(s);
  25.             if (list == null) return result;
  27.             for (String newState : list) {
  28.                 if (stateIsValid.apply(newState)) {
  29.                     if (visited.containsKey(newState)) {
  30.                         final int depth = visited.get(newState);
  31.                         if (depth < newDepth) {
  32.                             // do nothing
  33.                         } else if (depth == newDepth) {
  34.                             result.add(newState);
  35.                         } else {
  36.                             throw new IllegalStateException("not possible to get here");
  37.                         }
  39.                     } else {
  40.                         result.add(newState);
  41.                     }
  42.                 }
  43.             }
  45.             return result;
  46.         };
  48.         List<List<String>> result = new ArrayList<>();
  49.         q.offer(beginWord);
  50.         visited.put(beginWord, 0);
  51.         while (!q.isEmpty()) {
  52.             String state = q.poll();
  54.             // 如果当前路径长度已经超过当前最短路径长度，
  55.             // 可以中止对该路径的处理，因为我们要找的是最短路径
  56.             if (!result.isEmpty() && (visited.get(state) + 1) > result.get(0).size()) break;
  58.             if (stateIsTarget.apply(state)) {
  59.                 ArrayList<String> path = new ArrayList<>();
  60.                 genPath(father, beginWord, state, path, result);
  61.                 continue;
  62.             }
  63.             // 必须挪到下面，比如同一层A和B两个节点均指向了目标节点，
  64.             // 那么目标节点就会在q中出现两次，输出路径就会翻倍
  65.             // visited.insert(state);
  67.             // 扩展节点
  68.             List<String> newStates = stateExtend.apply(state);
  69.             for (String newState : newStates) {
  70.                 if (!visited.containsKey(newState)) {
  71.                     q.offer(newState);
  72.                     visited.put(newState, visited.get(state)+1);
  73.                 }
  74.                 ArrayList<String> parents = father.getOrDefault(newState, new ArrayList<>());
  75.                 parents.add(state);
  76.                 father.put(newState, parents);
  77.             }
  78.         }
  79.         return result;
  80.     }
  81.     private static void genPath(HashMap<String, ArrayList<String>> father,
  82.                                 String start, String state, List<String> path,
  83.                                 List<List<String>> result) {
  84.         path.add(state);
  85.         if (state.equals(start)) {
  86.             if (!result.isEmpty()) {
  87.                 if (path.size() < result.get(0).size()) {
  88.                     result.clear();
  89.                 } else if (path.size() == result.get(0).size()) {
  90.                     // do nothing
  91.                 } else {
  92.                     throw new IllegalStateException("not possible to get here");
  93.                 }
  94.             }
  95.             ArrayList<String> tmp = new ArrayList<>(path);
  96.             Collections.reverse(tmp);
  97.             result.add(tmp);
  98.         } else {
  99.             for (String f : father.get(state)) {
  100.                 genPath(father, start, f, path, result);
  101.             }
  102.         }
  103.         path.remove(path.size() - 1);
  104.     }
  106.     private static HashMap<String, HashSet<String>> buildGraph(Set<String> dict) {
  107.         HashMap<String, HashSet<String>> adjacency_list = new HashMap<>();
  108.         for (String word: dict) {
  109.             char[] array = word.toCharArray();
  110.             for (int i = 0; i < array.length; ++i) {
  111.                 final char old = array[i];
  112.                 for (char c = 'a'; c <= 'z'; c++) {
  113.                     // 防止同字母替换
  114.                     if (c == array[i]) continue;
  116.                     array[i] = c;
  117.                     String newWord = new String(array);
  119.                     if (dict.contains(newWord)) {
  120.                         HashSet<String> list = adjacency_list.getOrDefault(
  121.                                 word, new HashSet<>());
  122.                         list.add(newWord);
  123.                         adjacency_list.put(word, list);
  124.                     }
  125.                     array[i] = old; // 恢复该单词
  126.                 }
  127.             }
  128.         }
  129.         return adjacency_list;
  130.     }
  131. }

相关题目

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