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
For example,
Given:
start =
end =
dict =
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.
Solution:
BFS
public class Solution {
public ArrayList<ArrayList<String>> findLadders(String start, String end, HashSet<String> dict) {
//construct graph
HashMap<String, HashSet<String>> graph = new HashMap<String, HashSet<String>>();
dict.add(start);
dict.add(end);
for(String key : dict){
HashSet<String> neighbours = new HashSet<String>();
char[] chars = key.toCharArray();
for(int i = 0; i < chars.length; i++){
char c = chars[i];
for(char replace = 'a'; replace <='z'; replace ++){
if(replace == c) continue;
chars[i] = replace;
String temp = new String(chars);
if(dict.contains(temp)){
neighbours.add(temp);
}
chars[i] = c;
}
}
graph.put(key, neighbours);
}
return BFS(dict, graph, start, end);
}
public ArrayList<ArrayList<String>> BFS(HashSet<String> dict, HashMap<String, HashSet<String>> graph, String start, String end){
ArrayList<String> level = new ArrayList<String>();
level.add(start);
ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>();
HashMap<String, ArrayList<String>> predecessors = new HashMap<String, ArrayList<String>> ();
dict.remove(start);
predecessors.put(start, new ArrayList<String>());
while(!level.isEmpty()){
ArrayList<String> nextLevel = new ArrayList<String>();
for(String s : level){
HashSet<String> children = graph.get(s);
for(String child : children){
if(!dict.contains(child)) continue;
if(!nextLevel.contains(child))
nextLevel.add(child);
if(predecessors.containsKey(child)){
predecessors.get(child).add(s);
}else{
ArrayList<String> list = new ArrayList<String>();
list.add(s);
predecessors.put(child, list);
}
}
}
level = nextLevel;
dict.removeAll(level);
if(level.contains(end)){
buildPaths(result, predecessors, new ArrayList<String>(), end, start);
return result;
}
}
return result;
}
public void buildPaths(ArrayList<ArrayList<String>> result, HashMap<String, ArrayList<String>> predecessors, ArrayList<String> path, String current, String start){
path.add(0, current);
if(current.equals(start)){
result.add(path);
return;
}
for(String s : predecessors.get(current)){
ArrayList<String> nextPath = new ArrayList<String>(path);
buildPaths(result, predecessors, nextPath, s, start);
}
}
}
Two directions
In order to improve the performance, we try to traverse the graph starting from the both extremes and detecting when one has overlapped.public class Solution {
public ArrayList<ArrayList<String>> findLadders(String start, String end, HashSet<String> dict)
{
HashMap<String, HashSet<String>> neighborMap = new HashMap<String, HashSet<String>>();
HashMap<String, ArrayList<String>> predecessors = new HashMap<String, ArrayList<String>>();
for(String word: dict)
{
HashSet<String> neighbors = new HashSet<String>();
char[] wordArray = word.toCharArray();
for(int i=0; i< wordArray.length; i++)
{
char originalLetter = wordArray[i];
for (char newLetter = 'a'; newLetter<='z'; newLetter++)
{
if (newLetter == originalLetter)
continue;
wordArray[i] = newLetter;
if (dict.contains(new String(wordArray)))
neighbors.add(new String(wordArray));
}
wordArray[i] = originalLetter;
}
neighborMap.put(word, neighbors);
predecessors.put(word, new ArrayList<String>());
}
HashSet<String> fromBegin = new HashSet<String>();
HashSet<String> fromEnd = new HashSet<String>();
fromBegin.add(start);
fromEnd.add(end);
ArrayList<String> nextFromTop = new ArrayList<String>();
ArrayList<String> nextFromBottom = new ArrayList<String>();
ArrayList<String> actual;
nextFromTop.add(start);
nextFromBottom.add(end);
boolean isBeginTurn = true;
boolean completed = false;
while(!completed)
{
if(isBeginTurn)
{
HashSet<String> level = new HashSet<String>();
actual = nextFromTop;
if(actual.size()==0)
return new ArrayList<ArrayList<String>>();
nextFromTop = new ArrayList<String>();
for(String node: actual)
{
for(String child: neighborMap.get(node))
{
if(fromBegin.contains(child))
continue;
if(!level.contains(child))
{
nextFromTop.add(child);
level.add(child);
}
predecessors.get(child).add(node);
if(fromEnd.contains(child))
completed = true;
}
}
fromBegin.addAll(level);
isBeginTurn = false;
}
else
{
HashSet<String> level = new HashSet<String>();
actual = nextFromBottom;
if(actual.size()==0)
return new ArrayList<ArrayList<String>>();
nextFromBottom = new ArrayList<String>();
for(String node: actual)
{
for(String child: neighborMap.get(node))
{
if(fromEnd.contains(child))
continue;
if(!level.contains(child))
{
nextFromBottom.add(child);
level.add(child);
}
predecessors.get(node).add(child);
if(fromBegin.contains(child))
completed = true;
}
}
fromEnd.addAll(level);
isBeginTurn = true;
}
}
ArrayList<ArrayList<String>> solution =new ArrayList<ArrayList<String>>();
createSolution(start, end, predecessors, new ArrayList<String>(), solution);
return solution;
}
private void createSolution(String start, String word, HashMap<String, ArrayList<String>> predecessors, ArrayList<String> temp, ArrayList<ArrayList<String>> solution)
{
if (word == start)
solution.add(temp);
temp.add(0,word);
for(String newWord: predecessors.get(word))
{
createSolution(start, newWord, predecessors, (ArrayList<String>) temp.clone(), solution);
}
}
}
Comparisong of times we obtain for this complexity running Leetcode is around 6%: 1300ms vs 1224 ms
No comments :
Post a Comment