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
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.
Naive Way:This question is hard. I tried at least 100 times but only get one of my solution passed the OJ in 1800+ms. Hard problem can always classify people, so I need to pay more attention to this question. In word-ladder , I use a BFS approach, which is easy and quick to generate. What is different this time is that whether BFS or DFS, we need to mark each node that is visited. Consider this case:
start = 'red'
end = 'tax'
dict = ['ted', rad', 'tad']
since we cannot use a node twice, whether BFS or DFS will give us
either red->ted->tad->tax
or red->rad->tad->tax
because 'tad' is a common word in two paths.
A DFS with back-tracing is able to deal with that. But only DFS cannot ensure minimum steps. Thus, I apply level-order BFS first to put every word in a List<Set<String>> layer structure container, with the size of outer list equal to the minimum step. And apply DFS on this container to get each path. This is my first solution that get accepted. It takes 1400+ ms, while the average run time for this question is around 700ms.
public class Solution {
public List<List<String>> findLadders(String start, String end, Set<String> dict) {
List<List<String>> rslt = new ArrayList<List<String>>();
List<Set<String>> tree = new ArrayList<Set<String>>();
boolean found = false;
// initialize first layer of the tree
Set<String> first_layer = new HashSet<String>();
first_layer.add(start);
if(dict.contains(start)) dict.remove(start);
tree.add(first_layer);
// add end to dictionary
dict.add(end);
// level-order traversal to construct the tree
while(!found && tree.get(tree.size()-1).size()!=0){
Set<String> new_layer = new HashSet<String>();
Set<String> cur_layer = tree.get(tree.size()-1);
Iterator<String> iter = cur_layer.iterator();
while(iter.hasNext()){
String s = iter.next();
char[] chars = s.toCharArray();
for(int j = 0;j < s.length();j++){
char original = chars[j];
for(char c = 'a';c <= 'z';c++){
chars[j] = c;
String t = new String(chars);
if(t.equals(end)) found = true;
if(dict.contains(t)){
if(!t.equals(end)) dict.remove(t);
new_layer.add(t);
}
}
chars[j] = original;
}
}
tree.add(new_layer);
}
// dfs to construct paths
Stack<String> path = new Stack<String>();
path.push(start);
dfs(start, end, 1, path, tree, rslt);
return rslt;
}
private void dfs(String s, String end, int index, Stack<String> path, List<Set<String>> tree, List<List<String>> rslt){
if(s.equals(end)){
List<String> validPath = new ArrayList<String>();
validPath.addAll(path);
rslt.add(validPath);
return;
}
if(index >= tree.size()) return;
Set<String> set = tree.get(index);
char[] chars = s.toCharArray();
for(int j = 0;j < s.length();j++){
char original = chars[j];
for(char c = 'a';c <= 'z';c++){
chars[j] = c;
String t = new String(chars);
if(set.contains(t)){
path.push(t);
dfs(t, end, index+1, path, tree, rslt);
path.pop();
}
}
chars[j] = original;
}
}
}
Also, it is after several observation of others' code, I found that when listing the neighbors of a particular word, first convert it to char[] array and then replace a char instead of doing s.substring(0,i)+c+s.substring(i+1,s.length()) will save much time. It is probably because doing substring is initializing a new String each time, which is costly.
After seeing this post https://oj.leetcode.com/discuss/21902/java-solution-with-iteration on Discuss, I realized that DFS is not necessary. If I do a level-order traversal, delete the whole level from dict before traversal next level, I can efficiently deal with the case where a word is shared by to paths. Because a word shared by two paths must be at same location.
I give it a second trial using only BFS. And the code get accepted in 1000+ms.
public class Solution {
public List<List<String>> findLadders(String start, String end, Set<String> dict) {
List<List<String>> rslt = new ArrayList<List<String>>();
Deque<List<String>> paths = new LinkedList<List<String>>();
boolean found = false;
// initialize path
List<String> path = new ArrayList<String>();
path.add(start);
paths.offerLast(path);
// add end to dictionary, remove start from dict
dict.add(end);
if(dict.contains(start)) dict.remove(start);
// BFS
while(!found && !paths.isEmpty()){
Set<String> set = new HashSet<String>();
int k = paths.size();
for(int i = 0;i < k;i++){
List<String> list = paths.pollFirst();
String s = list.get(list.size()-1);
for(String t : neighbors(s, dict)){
set.add(t);
List<String> newList = new ArrayList<String>(list);
newList.add(t);
paths.offerLast(newList);
if(t.equals(end)){
found = true;
rslt.add(newList);
}
}
}
dict.removeAll(set);
}
return rslt;
}
private List<String> neighbors(String s, Set<String> dict){
List<String> list = new ArrayList<String>();
char[] chars = s.toCharArray();
for(int j = 0;j < s.length();j++){
char original = chars[j];
for(char c = 'a';c <= 'z';c++){
chars[j] = c;
String t = new String(chars);
if(dict.contains(t)) list.add(t);
}
chars[j] = original;
}
return list;
}
}
Improved Way: That is not enough. The highest run time distribution is around 700ms. I am far away from that yet. I looked into several posts about Word Ladder II. This two I found most helpful.
https://oj.leetcode.com/discuss/25970/java-modified-bfs-to-find-end-followed-dfs-reconstruct-paths
and http://yucoding.blogspot.com/2014/01/leetcode-question-word-ladder-ii.html (C++).
I found that the common point of their methods is to store the parents for each string instead of what is more straightforward, the children of each string. This reason for doing this is probably because storing the parents is using a lot less space than storing the children. (I tried storing children instead f parents, got MLE). Just Considering each word could have length * 26 at most children, while it will always have less than length*26 parents, since its neighbors selected by its parent cannot become its parent.
To put it simple, parent selects children, only when two parents are alike, they can select same children. Thus, given each word, the size of its parents is much more less than the size of its children.
The following code applies mapping a word to its parents and got accept in 600+ ms. I keep the finding neighbor function and adding a dfs to find paths based on the parent relationship map.
public class Solution {
public List<List<String>> findLadders(String start, String end, Set<String> dict) {
List<List<String>> rslt = new ArrayList<List<String>>();
Map<String, List<String>> parents = new HashMap<String, List<String>>();
boolean found = false;
// initialize
Set<String> cur_layer = new HashSet<String>();
cur_layer.add(start);
if(dict.contains(start)) dict.remove(start);
dict.add(end);
// BFS construct map
while(!found && !cur_layer.isEmpty()){
Set<String> new_layer = new HashSet<String>();
Iterator<String> iter = cur_layer.iterator();
while(iter.hasNext()){
String s = iter.next();
for(String t: neighbors(s, dict)){
new_layer.add(t);
if(!parents.containsKey(t)){
List<String> list = new ArrayList<String>();
list.add(s);
parents.put(t,list);
}else{
List<String> list = parents.get(t);
list.add(s);
}
if(t.equals(end)) found = true;
}
}
dict.removeAll(new_layer);
cur_layer = new_layer;
}
// DFS construct paths
Stack<String> path = new Stack<String>();
path.push(end);
dfs(start, end, path, parents, rslt);
return rslt;
}
private void dfs(String start, String s, Stack<String> path, Map<String, List<String>> parents, List<List<String>> rslt){
// base case
if(s.equals(start)){
List<String> list = new ArrayList<String>();
list.addAll(path);
Collections.reverse(list);
rslt.add(list);
return;
}
// edge case
if(!parents.containsKey(s)) return;
// recursion
for(String t: parents.get(s)){
path.push(t);
dfs(start, t, path, parents, rslt);
path.pop();
}
}
private List<String> neighbors(String s, Set<String> dict){
List<String> list = new ArrayList<String>();
char[] chars = s.toCharArray();
for(int j = 0;j < s.length();j++){
char original = chars[j];
for(char c = 'a';c <= 'z';c++){
chars[j] = c;
String t = new String(chars);
if(!t.equals(s) && dict.contains(t)) list.add(t);
}
chars[j] = original;
}
return list;
}
}
