Algorithms
The Word Ladder Game – Word Navigation
Change a word into another by changing only only one character at a time. All intermediate words should be contained in a dictionary.
This problem is pretty simple if we can choose a proper data structure. Let’s begin with a simple example. Say, we have a dictionary of words, the word to navigate from. and the word we need to navigate into.
Dictionary: {“DOG”, “COT”, “COG”, “FOG”, “DOT”}, source: “FOG”, and destination: “COT”
We can navigate from “FOG” by changing ‘F’ into [‘A’ – ‘Z’] except ‘F’. So, there will be 25 different transformed words. But we are only allowed to use only those exist in the dictionary. In this case we have 2 words : {“COG”, “DOG”}
If one of the transformed word matches with the target then our search was successful. If not then we can apply the same navigation procedure on this valid transformed word. If none of the valid transformed word lead us to the solution then we need to back track and follow the same procedure for the next character position. If the procedure didn’t find the target word then we fail the search.
For example: ‘COG’ can to transformed into ‘COT’ by changing character in 3rd position (‘G’ to ‘T’). So, the path was: ‘FOG’ –> ‘COG’ –> ‘COT’.
Now, which data structure and algorithm should we use? It sounds like a breadth first search , right? Exactly! We can use a queue to perform BFS. Below is a O(n) solution for this problem using LinkedList as for queue operation.
public static boolean isNavigable(final String src, final String dst, final Set<String> dictionary) {
if (src.length() != dst.length()) {
return false;
}
if (src.equals(dst)) {
return true;
}
dictionary.remove(src);
final LinkedList<String> q = new LinkedList<String>();
q.add(src);
while (!q.isEmpty()) {
final String intermediate = q.remove();
for (int i = 0; i < intermediate.length(); i++) {
char[] candidateChars = intermediate.toCharArray();
for (char j = 'A'; j < 'Z'; j++) {
candidateChars[i] = j;
final String candidate = new String(candidateChars);
if (candidate.equals(dst)) {
System.out.print("-->" + candidate);
return true;
} else if (dictionary.contains(candidate)) {
dictionary.remove(candidate);
q.add(candidate);
System.out.print("-->" + candidate);
}
}
}
}
return false;
}
How to find all possible shortest transformations?
For example, Dictionary = [“hot”, “dot”, “dog”, “lot”, “log”, “lob”, “cob”];
Then, to navigate from src = “hit” to dest = “cog”, we can have 3 possible paths as follows –
hit
|
hot
/ \
dot lot
| / \
dog log lob
| | |
cog cog cob
|
cog
But the shortest paths are [hit–>hot–>dot–>dog–>cog, hit–>hot–>lot–>log–>cog] of total 4 transformations. How to extend our previous solution to achieve this?
Note that, while we are traversing in BFS we can maintain the total numbers of transformations. We can use this as the length of a path from the source word. If current transformation (i.e. a candidate word that presents in dictionary) was previously generated by some other intermediate word then we have two choice – either take this path if it leads to a shorter path to solution then the previous path or don’t take current path and discard this transformation. We can easily do this using Dijkstra’s shortest path invariant where we only update a neighbor path len when pathLen[mine]+1 <= pathLen[neighbor]. Also, we each time we select a transformed candidate word to visit , we will update its parent to the the intermediate word it is transformed from so that later we can reconstruct the path.
Below is an implementation of the above approach using O(n) space and O(n) time.
public static List<List<String>> wordLadderAll(Set<String> dictionary, String src, String dst){
if(src == null || dst == null || dictionary == null || src.isEmpty() || dst.isEmpty() || dictionary.isEmpty()){
return Collections.EMPTY_LIST;
}
//Queue to traverse in BFS
Queue<String> queue = new ArrayDeque<String>();
//path from a node to its parent along the BFS traversal
Map<String, String> parent = new HashMap<String, String>();
//level of a word appeared in the DAG
Map<String, Integer> pathLen = new HashMap<String, Integer>();
//min length path so far
int minLen = Integer.MAX_VALUE;
//resulting shortest paths
List<List<String>> paths = new ArrayList<>();
//resulting shortest path last nodes
Set<String> shortestPathLeaves = new HashSet<String>();
//add source to queue to start traversing
queue.add(src);
pathLen.put(src, 0);
while(!queue.isEmpty()){
String intermediate = queue.poll();
//we already have a shortest path, so discard this longer path
if(pathLen.get(intermediate) >= minLen){
continue;
}
//BFS to each possible 1 edit distance neighbors in dictionary
for(int i = 0; i<intermediate.length(); i++){
char[] candidateChars = intermediate.toCharArray();
//all possible words with current character variations
for(char c = 'a'; c < 'z'; c++){
candidateChars[i] = c;
String candidate = new String(candidateChars);
if(!pathLen.containsKey(candidate)){
pathLen.put(candidate, Integer.MAX_VALUE);
}
//Dijktra's shortest path formullae
if(pathLen.get(intermediate)+1 > pathLen.get(candidate)){
continue;
}
//if we reach a solution, add it to solution
if(candidate.equals(dst)){
shortestPathLeaves.add(intermediate);
minLen = Math.min(minLen, pathLen.get(intermediate)+1);
}
//otherwise if this intermediate word is present in dictionary then
//add it as children and update the path len
else if(dictionary.contains(candidate)){
parent.put(candidate, intermediate);
pathLen.put(candidate, pathLen.get(intermediate)+1);
queue.add(candidate);
}
}
}
}
//Add all paths to result set
for(String path : shortestPathLeaves){
paths.add(getPath(parent, path, src, dst));
}
return paths;
}
private static List<String> getPath(Map<String, String> parentMap, String leaf, String src, String dst){
List<String> path = new ArrayList<String>();
String node = leaf;
path.add(dst);
path.add(0, leaf);
while(parentMap.get(node) != null && parentMap.get(node) != src){
node = parentMap.get(node);
path.add(0, node);
}
path.add(0, src);
return path;
}