Problem
Given a same length words dictionary and start and target words in the dictionary, find the shortest distance from start to target. Adjacent words are words with of one character difference. For example: given dictionary {pool, poon, loon, loan, tool, toor} start: pool, target: loan, the output should be 4, because pool -> poon -> loon -> loan.
Solution
Instinct told us this is a bfs traversal problem.
We have been talking about graph traversal for a while, in the context of saying it is an overkill. The main overhead for graph is to iterate the array elements in order to build the graph, besides, an extra space of V + E is needed to store the graph.
Most of the time, the reason we build a graph is to quickly get g.adj(v) array for bfs and dfs. Without a graph datastructure, we can still get g.adj(v), only not that quickly. The following solution is a poor man's bfs without graph datastructure.
import java.util.*;
public class PoolmanBfs {
private static boolean isAdjacent(String a, String b) {
int diff = 0;
for(int i = 0; i < a.length(); i++){
if(a.charAt(i) != b.charAt(i)) {
diff ++;
if(diff > 1)
return false;
}
}
return diff == 1;
}
private static class CountedNode {
String word;
int len;
}
public static int dfs(Set<String> dictionary, String start, String target) {
Queue<CountedNode> queue = new LinkedList<>();
CountedNode cn = new CountedNode();
cn.word = start;
cn.len = 1;
queue.add(cn);
while(!queue.isEmpty()) {
CountedNode curr = queue.poll();
Iterator<String> it = dictionary.iterator();
while(it.hasNext()) {
String tmp = it.next();
if(isAdjacent(curr.word, tmp)) {
cn = new CountedNode();
cn.word = tmp;
cn.len = curr.len + 1;
queue.add(cn);
it.remove();
if(tmp.equals(target)) {
return cn.len;
}
}
}
}
return 0;
}
public static void main(String...args) {
Set<String> dic = new HashSet<>();
dic.add("poor");
dic.add("pool");
dic.add("poon");
dic.add("loon");
dic.add("loan");
dic.add("tool");
dic.add("toor");
System.out.println(dfs(dic, "poor", "loan"));
}
}
The time complexity is still O(N^2*m), where N is the number of dictionary words and m is the word length. Extra space is bound by bfs queue size, which is O(N).
