# LeetCode Question -- Word Ladder II

### Question:

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.

### Analysis:

II的解法也有很多种，但是却不容易[AC]通过，主要原因是时间复杂度太大： 造成时间复杂度过大的可能有两个原因：

(题外话：我称这种为小学生思路，因为我觉得如果让一个小学生来做这类题目，他们可能往往想到的就是这种最朴素的解决办法。而由于大部分程序员的思路会受到刷题训练的限制，往往想到iteration就是用while或者for loop来遍历，而忽略了看似简单幼稚，实则可能更实用的解法)

(1) 在__原因1.__解决的前提下，既然用BFS去寻找第一条最短路径是肯定不会超时的，那么如果我用一个时间复杂度不大于BFS的算法去找出所有路径，也不会超时；

(2) 我先想到了DFS，但是还不知道如何应用DFS去解决。我先在纸上画出了BFS的队列模型，试着找出线索。

start = hit
end = cog
dict = [hot,dot,dog,lot,log,dof,mit,sit,set,mog,mig,seg,nax,max]
</p>

Return

  [["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"],
["hit","mit","mig","mog","cog"]]


level 1: [hit]
level 2: [mit, sit, hot]
level 3: [mig, set, dot, lot]
level 4: [mog, seg, dof, dog, log]
level 5: [cog]

(1) 字典中其他尚未遍历到的单词，比如”nax”和”max”，如何处理，是否可以被忽略？ 必要性

(2) BFS建立的层级结构，它包含了所有可能构成最短路径的word吗？ 充分性

### Code:

• String changeChar(String s, int i, char c) 替换String s中位置为i的char为c；
• boolean canTransform(String s1, String s2) String s1是否可以更改一个char变为s2。

• List<List<String>> findLadders(String start, String end, Set<String> dict) 主函数，包含BFS建立层级结构的实现，和调用DFS返回结果；
• List<List<String>> dfsPathDP(List<List<String>> levels, int level, String start, String end, HashMap<String,List<List<String>>> cache) DFS遍历：List<List<String>> levels是BFS建立的层级结构，int level是当前层级数，String start是上一层level所选择的word，String end是最短路径终止word，HashMap用来做DP Cache。

class WordLadderII_Refact {
static List<List<String>> findLadders(String start, String end, Set<String> dict) {
List<List<String>> res = new ArrayList<List<String>>();

if (canTransform(start, end)) {
List<String> path = new ArrayList<String>();
return res;
}

List<String> bfs = new ArrayList<String>();
int level = 1;
int begin = 0;
/* a HashMap could be both 1) track explored and 2) length calculate
* but we alread have Set<String> dict to track the explored */
HashMap<String, Integer> explored = new HashMap<String, Integer>();
explored.put(start, 0);
dict.remove(start);
dict.remove(end);

List<List<String>> levels = new ArrayList<List<String>>();

int minLength = -1;
outer:
while (begin < bfs.size()) {
if (minLength >= 0) { //!!!
break;
}

int tail = bfs.size();
if (levels.size() == level - 1) {
}

for (int i = begin; i < tail; i++) {
String curr = bfs.get(i); // get(i)
for (int j = 0; j < curr.length(); j++) {
for (char c = 'a'; c <= 'z'; c++) {
String s = changeChar(curr, j, c);

//!!! dict Set MAY NOT include "start & end"
if(s.equals(end)) { //!!! FOUND min path
explored.put(end, level);
minLength = level + 1;

break outer;
}

if (dict.contains(s) && !explored.containsKey(s)) {
explored.put(s, level);
dict.remove(s);
// add s into its level
}
} // end of inner for
}
} // end of outer for each level
level++;
begin = tail;
} // end of while

if (minLength == -1) {
return res;
}

/* DFS DP */
HashMap<String, List<List<String>> > cache =
new HashMap<String, List<List<String>> >();
return dfsPathDP(levels, 0, start, end, cache);
}

static List<List<String>> dfsPathDP(List<List<String>> levels,
int level, String start, String end,
HashMap<String,List<List<String>>> cache)
{
if (cache.containsKey(start)) {
return cache.get(start);
}

if (level == levels.size()) {
if (start.equals(end)) {
List<String> pathEnd = new ArrayList<String>();
List<List<String>> endRes = new ArrayList<List<String>>();
cache.put(start, endRes);
return cache.get(start);
} else {
return null;
}
}

List<List<String>> res = new ArrayList<List<String>>();

List<String> currLevel = levels.get(level);
for (String s : currLevel) {
if (!canTransform(start, s)) {
continue;
}
List<List<String>> tailingRes = dfsPathDP(levels,
level + 1, s, end, cache);
if (tailingRes == null) { //!!!
continue;
}
for (List<String> path : tailingRes) {
List<String> newPath = new ArrayList<String>();
}
} // end outer for

cache.put(start, res);
return res;
}

static String changeChar(String s, int i, char c) {
StringBuilder sb = new StringBuilder(s);
sb.setCharAt(i, c);
return sb.toString();
}

static boolean canTransform(String s1, String s2) {
/* a very simple version cause string is determined in length */
int diff = 0;
for (int i = 0; i < s1.length(); i++) {
if (s1.charAt(i) != s2.charAt(i)) {
if (diff == 0) {
diff++;;
} else {
return false;
}
}
}
return true;
}

public static void main(String[] args) {
String start = "hit";
String end = "cog";
Set<String> dict = new HashSet<String>();
String[] dictArray = new String[]{"hot","dot","dog","lot","log","dof","mit","sit","set","mog","mig","seg"};
for (String s : dictArray) {
}

List<List<String>> res = findLadders(start, end, dict);
System.out.println(res.size());
for (List<String> path : res) {
System.out.println(path);
}
}
}


Coding上的优化可以是在BFS建层级结构那段，我用了比较不常用的outer loop标记；

### Also see:

zsxwing / leetcod-java

Yu’s Coding Garden

“一亩三分地”上也有讨论这个问题的帖子

 Tweet