CareerCup

Well, probably this is an algorithm probelm instead of a design problem. Convert to an directed graph, every word as a node and any two words with only one character different have one edge with weight 1 connecting them. From the source node to the target node, it's like find a path between them, then you can use Dijkstra's algorithm or Dp and the path is the answer.

will edit distance algorithm solve the problem ?

Look at careercup.com/question?id=14722757

This works:

public static int levenshteinDistance(String src, String target){

int srcLen = src.length();
int targetLen = target.length();
int cost = 0;

if(srcLen <= 0 || targetLen <= 0){
return 0;
}

if(src.charAt(srcLen-1) != target.charAt(targetLen-1)){
cost = 1;
}

if(srcLen == 0){
return targetLen;
}else if(targetLen == 0){
return srcLen;
}else{
return Math.min(Math.min(levenshteinDistance(src.substring(0, srcLen-1), target) + 1,
levenshteinDistance(src, target.substring(0, targetLen - 1)) + 1),
levenshteinDistance(src.substring(0, srcLen - 1), target.substring(0, targetLen - 1)) + cost);
}


}

example: turn DAMP to LIMB thru ... DAMP -> LAMP -> LIMP -> LIMB ... construct a binary tree to store all meaningful words, then do a BST...that shud do it...

We have a set of words from the dictionary that we can look up.

We first compute the levenshtein distance between the two candidate words and save it in a temp variable.

1.
Then choose a list of words from the dictionary of the same length as the destination word and such that there is only one character change in the source word. ( also read as the levenshtein distance is 1 ).

for e.g. damp -> limbs

damp -> damps -> lamps -> limps -> limbs

So now we have listOfWords[] such that they differ only by one character in the source.

2.
Now from this listOfWords[], compute the levenshtein distance of listOfWords[i] and destination word and choose only those set of words which have the least distance from the destination word.

Repeat steps 1 & 2 till we have the destination word, in course of which we maintain the words chosen to reach this destination word.

One of the way to do could be
1. construct a DAWG (directed acyclic word graph) of all meaningful word formed by first letter to source word ateast equivalent to final word.
As given only one character change at a time is allowed thus there should exist a path where if in above constructed DAWG if the initial word is replaced with first letter of final word it would lead to final word.

For exam:
head -> tail

transformation may will include: head->heal->hell->hall->hail->tail

DAWG for head includes: head,heal, hell, hall, hail, etc.

thus if we traverse DAWG comparing all letters after first letter, we should get a path to reach hail (i.e. tail when h is replaced by tail).

Wil this work?

See the "EDIT-DISTANCE PROBLEM" in wiki

how abt using Tries?

cann you give some example, question is not clear