126.Word-Ladder-II

126. Word Ladder II

题目地址

http://www.lintcode.com/problem/word-ladder-ii/description

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

题目描述

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

Only one letter can be changed at a time
Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

Note:
Return an empty list 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:
[
  ["hit","hot","dot","dog","cog"],
  ["hit","hot","lot","log","cog"]
]

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

Output: []

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

代码

Approach #1 BFS + DFS

• BFS to get neighbors, (双set, 保证层级有序)

  • visited.contains(next) || start.contains(next)

• DFS backtrack to get paths

BFS 中用两个set，而不用queue是因为防止start.contains(next)误算下层的元素

class Solution {
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
      Set<String> dict = new HashSet<>(wordList);
      List<List<String>> res = new ArrayList<>();
      if (!dict.contains(endWord))   return res;

      // bfs to get neighbors
      Map<String, List<String>> map = getNeighbors(beginWord, endWord, dict);
      // dfs
      List<String> path = new ArrayList<>();
      path.add(beginWord);
      dfs(beginWord, endWord, map, res, path);
      return res;
    }

    public void dfs(String beginWord, String endWord, Map<String, List<String>> map, List<List<String>> res, List<String> path) {
      if (beginWord.equals(endWord)) {
          res.add(new ArrayList<>(path));
      }
      if (!map.containsKey(beginWord)) {
          return;
      }
      for (String next: map.get(beginWord)) {
          path.add(next);
          dfs(next, endWord, map, res, path);
          path.remove(path.size() - 1);
      }
    }

    // bfs
     public Map<String, List<String>> getNeighbors(String beginWord, String endWord, Set<String> dict) {
      Map<String, List<String>> map = new HashMap<>();

      Set<String> start = new HashSet<>();
      start.add(beginWord);
      Set<String> visited = new HashSet<>();

      while (!start.isEmpty()) {
          Set<String> set = new HashSet<>();
          for (String cur : start) {
              visited.add(cur);
              for (String next : getNext(cur, dict)) {
                  if (visited.contains(next) 
                      || start.contains(next)) {
                      continue;
                  }

                  set.add(next);
                  map.putIfAbsent(cur, new ArrayList<>());
                  map.get(cur).add(next);
              }
          }
          start = set;
      }
     return map;
    }

    private List<String> getNext(String cur, Set<String> dict) {
      List<String> res = new ArrayList<>();
      char[] chars = cur.toCharArray();
      for (int i = 0; i < chars.length; i++) {
          for (char c = 'a'; c <= 'z'; c++) {
              if (c == cur.charAt(i)) continue;
              String next = cur.substring(0, i) + c + cur.substring(i + 1);
              if (dict.contains(next)) {
                  res.add(next);
              }
          }
      }
      return res;
    }
}

Approach #2 BFS + DFS （RLE - Rejected）

• 先用BFS生成邻接单词表map和每个单词距离表distance

• 再用DFS遍历每条路径path, 利用distance保证次序

class Solution {
    public List<List<String>> findLadders(String start, String end, Set<String> dict) {
    // Used to store all path results
    List<List<String>> ladders = new ArrayList<List<String>>();
    // Used to save adjacent words
    Map<String, List<String>> map = new HashMap<String, List<String>>();
    // Calculate the distance from start to each word
    Map<String, Integer> distance = new HashMap<String, Integer>();

    dict.add(start);
    // dict.add(end); The last string is not included according to the assignment

    bfs(map, distance, start, end, dict);

    // Used for temporary paths in DFS
    List<String> path = new ArrayList<String>();

    dfs(ladders, path, start, end, distance, map);

    return ladders;
  }

    private void bfs(Map<String, List<String>> map, Map<String, Integer> distance, String start, String end, Set<String> dict) {
    Queue<String> q = new LinkedList<String>();
    q.offer(start);
    distance.put(start, 0);
    for (String s: dict) {
      map.put(s, new ArrayList<String>());
    }

    while (!q.isEmpty()) {
      String cur = q.poll();

      List<String> nextList = getNextList(cur, dict);
      for (String next : nextList) {
        map.get(next).add(cur);

        if (!distance.containsKey(next)) {
          distance.put(next, distance.get(cur) + 1);
          q.offer(next);
        }

      }
    }
  }

  private void dfs(List<List<String>> ladders, List<String> path, String start, String end, Map<String, Integer> distance, Map<String, List<String>> map) {
    path.add(start);
    if (start.equals(end)) {
      ladders.add(new ArrayList<String>(path));
    } else {
      for (String next : map.get(start)) {
        if (distance.containsKey(next) && distance.get(start) + 1 == distance.get(next)) {
          dfs(ladders, path, next, end, distance, map);
        }
      }
    }
    path.remove(path.size() - 1);
  }

  private List<String> getNextList(String cur, Set<String> dict) {
    List<String> nextList = new ArrayList<String>();
    for (int i = 0; i < cur.length(); i++) {
      for (char ch = 'a'; ch <= 'z'; ch++) {
        if (ch != cur.charAt(i)) {
          String newWord = cur.substring(0, i) + ch + cur.substring(i + 1);
          if (dict.contains(newWord)) {
            nextList.add(newWord);
          }
        }
      }
    }
    return nextList;
  }

}