Only one letter can be changed at a time
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"]
]
Idea: Dijkstra's algorithm. Image the words as nodes and the ladder as edges, this is exactly a shortest path problem from the node start (source) to the node end (destination). Without the Boost library in C++, we need to a little bit patience to implement the Dijkstra's algorithm in Java.
First add the start and the end to the dictionary. Then use breadth-first search to flood from the start node to all the reachable nodes (even further than end nodes), and label the distance between the current node and the start node. At the same time, for each node, create single direction edges to its source.
After the flood, start from the end node to construct path to the start node, since the edges we constructed are single directional and are from destination to source. Assume the distance between the node and the start node is x, then the next hop y of this node should follow two conditions:
1) y is x's neighbor (has constructed edge)
2) distance[y=>start]==distance[x=>start]-1
So following these two rules, use depth-first search to construct the path until the start node is reached. Do not forget to reverse the paths constructed before output, since the requirement is source to destination.
Time: O(n^2) (The fastest implementation of Dijkstra's algorithm is O(e+vlgv))
Space: O(n^2)
Code:
public class Solution {
public List<List<String>> findLadders(String start, String end, Set<String> dict) {
List<List<String>> result=new ArrayList<List<String>>();
if(dict==null||dict.size()==0)
return result;
HashMap<String,List<String>> graph=new HashMap<String,List<String>>();
HashMap<String, Integer> distance=new HashMap<String,Integer>();
dict.add(start);
dict.add(end);
bfs(graph,distance,start,end,dict);
List<String> path=new ArrayList<String>();
dfs(result,path,graph,distance,start,end);
return result;
}
public void dfs(List<List<String>> result,List<String> path, HashMap<String,List<String>> graph,HashMap<String,Integer> distance,String start,String cur)
{
path.add(cur);
if(path.contains(start))
{
Collections.reverse(path);
result.add(new ArrayList<String>(path));
Collections.reverse(path);
}
else
{
for(String next:graph.get(cur))
{
if(distance.containsKey(next)&&distance.get(cur)==distance.get(next)+1)
{
dfs(result,path,graph,distance,start,next);
}
}
}
path.remove(path.size()-1);
}
public void bfs(HashMap<String,List<String>> graph, HashMap<String,Integer> distance,String start, String end, Set<String> dict)
{
Queue<String> queue=new LinkedList<String>();
queue.offer(start);
distance.put(start,0);
for(String s:dict)
{
graph.put(s,new ArrayList<String>());
}
while(queue.isEmpty()==false)
{
String cur=queue.poll();
List<String> neighbors=getNeighbors(cur,dict);
for(String neighbor:neighbors)
{
graph.get(neighbor).add(cur);
if(distance.containsKey(neighbor)==false)
{
distance.put(neighbor,distance.get(cur)+1);
queue.offer(neighbor);
}
}
}
}
public List<String> getNeighbors(String cur, Set<String> dict)
{
List<String> result=new ArrayList<String>();
for(int i=0;i<cur.length();i++)
{
for(char c='a';c<='z';c++)
{
if(c!=cur.charAt(i))
{
String maybe=replaceCharAt(cur,i,c);
if(dict.contains(maybe))
result.add(maybe);
}
}
}
return result;
}
public String replaceCharAt(String s, int index, char c)
{
char[] chars=s.toCharArray();
chars[index]=c;
return new String(chars);
}
}
