Word Ladder

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

1. Only one letter can be changed at a time

2. Each intermediate word must exist in the word list

For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:

• Return 0 if there is no such transformation sequence.

• All words have the same length.

• All words contain only lowercase alphabetic characters.

分析

典型的BFS题。一层一层的找，分别对应修改一个字符，两个字符，三个字符...直至发现结尾字符串, 注意用一个Set寸已经访问过的字符串，避免重复。

复杂度

time: O(n), space: O(n)

代码

public class Solution {    public int ladderLength(String beginWord, String endWord, Set<String> wordList) {Queue<String> q = new LinkedList<String>();        q.add(beginWord);        Set<String> visited = new HashSet<String>();        visited.add(beginWord);        int level = 0;    while (!q.isEmpty()) {int len = q.size();level++;for (int i = 0; i < len; i++) {    String word = q.remove();    for (int j = 0; j < word.length(); j++) {        char[] chars = word.toCharArray();        for (char c = 'a'; c <= 'z'; c++) {chars[j] = c;String nextWord = new String(chars);if (nextWord.equals(endWord)) {return level + 1;}if (!visited.contains(nextWord) && wordList.contains(nextWord)) {q.add(nextWord);visited.add(nextWord);}        }    }}        }    return 0;    }}

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:

1. Only one letter can be changed at a time

2. Each intermediate word must exist in the word list

For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["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.

分析

如果要返回所有的结果，问题变复杂了些。因为用BFS相对于DFS的劣势就是不方便存储结果。这种需要返回所有结果的，还是应该从DFS考虑，但是直接应用DFS复杂度会很高，因为这道题我们只要知道结尾就好了，不用继续往下搜。

所以问题就转化成怎样用DFS的同时又可以限制DFS的深度，所以我们可以BFS与DFS结合。先用BFS搜到结尾字符串，然后把中途所有的字符串及其跟起始字符的edit distance存在一个map里。这样的话，我们就可以从结尾字符串开始DFS，只有Map内的字符串才考虑继续DFS，直至搜到起始字符。

注意这里有个小技巧，就是为什么不从起始字符串开始DFS直至搜到结尾字符串，而是反过来。这里可以脑子里想像一个图，如果从起始字符串开始搜，到最后一层的话会有很多无效搜索，因为那层我们只需要找到结尾字符串，那么多无效的搜索到最一层太浪费时间。反之，如果我们从结尾字符串开始DFS, 我们把起始层控制在一个字符串，整个图先越来越宽，然后越来越窄直到起始字符串，而非一直越来越宽直到结尾字符串那层。

复杂度

time: O(n), space: O(n)

代码

public class Solution {    public List<List<String>> findLadders(String beginWord, String endWord, Set<String> wordList) {        Map<String, Integer> distMap = new HashMap<String, Integer>();         getDistance(beginWord, endWord, wordList, distMap);        List<List<String>> res = new ArrayList<List<String>>();        dfs(res, new ArrayList<String>(), distMap, wordList, endWord, beginWord);        return res;    }        public void dfs(List<List<String>> res, List<String> cur, Map<String, Integer> distMap, Set<String> wordList, String word, String des) {        if (word.equals(des)) {List<String> list = new ArrayList<String>(cur);list.add(des);Collections.reverse(list);res.add(list);return;        }    cur.add(word);        for (int i = 0; i < word.length(); i++) {char[] chars = word.toCharArray();for (char c = 'a'; c <= 'z'; c++) {    chars[i] = c;    String nextWord = new String(chars);    // 不仅字典中含有，两字符串也是要在路径的相邻位置即距离差1    if (distMap.containsKey(nextWord) && distMap.get(nextWord) == distMap.get(word) - 1) {        dfs(res, cur, distMap, wordList, nextWord, des);    }}        }        cur.remove(cur.size() - 1);    }        // 用Word Ladder I的方法把候选字符串及其距离存入map，缩小DFS范围。    public void getDistance(String beginWord, String endWord, Set<String> wordList, Map<String, Integer> distMap) {        distMap.put(beginWord, 1);        Queue<String> q = new LinkedList<String>();        q.add(beginWord);    while (!q.isEmpty()) {String word = q.remove();for (int j = 0; j < word.length(); j++) {    char[] chars = word.toCharArray();    for (char c = 'a';  c <= 'z'; c++) {        chars[j] = c;        String nextWord = new String(chars);        if (nextWord.equals(endWord)) {distMap.put(nextWord, distMap.get(word) + 1);return;        }        if (wordList.contains(nextWord) && !distMap.containsKey(nextWord)) {distMap.put(nextWord, distMap.get(word) + 1);q.add(nextWord);        }    }}        }    }}