The first one:
Given two words (start and end), and a dictionary, find the length of shortest transformation sequence 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 = "hit"
end = "cog"
dict = ["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.
A typical
BFS problem. Start from "start", we go through all possible replacements and see if we can find some transformations in the dict. If we can, we put the intermediate word in the queue. The queue always stores transformations of words in the current level. (e.g, "dot" and "lot" will both be placed in the queue after "hot" is polled). Whenever "end" is reached, we return the length + 1, where "+ 1" indicates the "end" string.
public class Solution {
public int ladderLength(String start, String end, Set dict) {
if (dict == null || dict.size() == 0)
return 0;
if (start.equals(end))
return 1;
int length = 1;
Queue queue = new LinkedList ();
queue.offer(start);
dict.remove(start);
while (!queue.isEmpty())
{
//for multiple transformations, we only want to increment length once,
// thus only increment length after current stage of transformation is done
int size = queue.size();
for (int j = 0; j < size; j++)
{
String current = queue.poll();
for (char c = 'a'; c <= 'z'; c++)
{
for (int i = 0; i < current.length(); i++)
{
if (current.charAt(i) == c)
continue;
String tmp = replace(current, i, c);
if (tmp.equals(end))
return length + 1;
if (dict.contains(tmp))
{
//it is possible that another replacement of the character will lead to a shorter length,
//thus length cannot be incremented here
//e.g., "a", "b", "c", if length is incremented at b, we will have one extra count
queue.offer(tmp);
dict.remove(tmp);
}
}
}
}
//if no transformation is found, queue is empty, and we will exit the loop and return 0
// otherwise we assume one transformation is found
length++;
}
return 0;
}
private String replace(String s, int pos, char character)
{
char[] current = s.toCharArray();
current[pos] = character;
return new String(current);
}
}
The second one:
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 = "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.
This problem is hard one because of the time and memory complexity.
Word Ladder I is a typical BFS problem, so for this one, intuitively we would think of using BFS too.
Not yet done...
Because we need to return every possible shortest path, we cannot simply remove the used words ("hot" is used in both paths). A possible approach can be as follows:
1. Do BFS first.
Use a map<String, ArrayList<String>> to track all possible transformations to the key String. e.g., "cog", {"dog", "log"};
Use another map<String, Integer> to track the level of the string. e.g., "hot", 1; "cog", 5;
2. The transformation is achieved by the same method as we used in the first problem.
3. Do DFS.
From the "end" string, search the map and get the previous strings, until the start string is reached.
Reverse the path (because we search from the end to the start) and return the path.
Note:
Difference between Backtracking and DFS.
Backtracking is a more general purpose algorithm. It can be used on any type of structure where portions of the domain can be eliminated.
DFS is a specific form of backtracking related to searching tree structures, and is limited to a tree structure.
public class Solution {
public ArrayList> findLadders(String start, String end, Set dict) {
ArrayList> ladders = new ArrayList> ();
if (start.equals(end))
return ladders;
HashMap> prevWord = new HashMap>();
HashMap level = new HashMap ();
dict.add(start);
dict.add(end);
getTransformation(prevWord, level, start, dict);
ArrayList path = new ArrayList();
getPath(ladders, path, prevWord, level, end, start);
return ladders;
}
//apply DFS
private void getPath(ArrayList> ladders, ArrayList path,
HashMap> prevWord, HashMap level, String curr, String start)
{
path.add(curr);
if (curr.equals(start))
{
Collections.reverse(path);
ladders.add(new ArrayList(path));
Collections.reverse(path);
}
else
{
for (String word : prevWord.get(curr))
{
if (level.containsKey(word) && level.get(curr) == level.get(word) + 1)
getPath(ladders, path, prevWord, level, word, start);
}
}
// should be outside the loop since we add the word at the beginning of the method
path.remove(path.size() - 1);
}
//applying BFS
private void getTransformation(HashMap> prevWord, HashMap level,
String start, Set dict)
{
Queue queue = new LinkedList();
queue.offer(start);
for (String s : dict)
prevWord.put(s, new ArrayList());
level.put(start, 0);
while (!queue.isEmpty())
{
String curr = queue.poll();
ArrayList list = transformWord(curr, dict);
for (String word : list)
{
//prevWord tracks the word before
//the key is the word transformed from the value
//curr is the word before the next
prevWord.get(word).add(curr);
//if level already contains the word, it means the word is at the upper level
//we do not want to change it to a lower level
if (!level.containsKey(word))
{
level.put(word, level.get(curr) + 1);
queue.offer(word);
}
}
}
}
private ArrayList transformWord(String s, Set dict)
{
ArrayList transformations = new ArrayList();
for (char c = 'a'; c <= 'z'; c++)
{
for (int i = 0; i < s.length(); i++)
{
if(s.charAt(i) == c)
continue;
String tmp = s.substring(0,i) + c + s.substring(i + 1);
if (dict.contains(tmp))
transformations.add(tmp);
}
}
return transformations;
}
}
