I came across this variation of edit-distance problem:
Design an algorithm which transforms a source word to a target word. for example: from head to tail, in each step, you just can replace one character, and the word must be valid. You'll be given a dictionary.
It clearly is a variation of the edit distance problem, but in edit distance I do not care about if the word is valid or not. So how do I add this requirement to edit distance.
This can be modelled as a graph problem. You can think of the words as nodes of the graph and two nodes are connected if and only if they are of same length and differ in one char.
You can preprocess the dictionary and create this graph, should look like:
stack jack
| |
| |
smack back -- pack -- pick
You can then have a mapping from the word to the node representing the word, for this you can use a hash table, height balanced BST ...
Once you have the above mapping in place, all you have to do is see if there exists a path between the two graph nodes, which can easily be done using BFS or DFS.
So you can summarize the algorithm as:
preprocess the dictionary and create the graph.
Given the two inputs words w1 and w2
if length(w1) != length(w2)
Not possible to convert
else
n1 = get_node(w1)
n2 = get_node(w2)
if(path_exists(n1,n2))
Possible and nodes in the path represent intermediary words
else
Not possible
codaddict's graph approach is valid, though it takes O(n^2) time to build each graph, where n is the number of words of a given length. If that's a problem, you can build a bk-tree much more efficiently, which makes it possible to find all words with a given edit distance (in this case, 1) of a target word.
I don't think this is edit distance.
I think this can be done using a graph. Just construct a graph from your dictionary, and attempt to navigate using your favorite graph traversal algorithm to the destination.
@Codeaddict solution is correct but it misses on the opportunity to simplify and optimize the solution.
DFS vs BFS:
If we go with DFS, there are chances that we meet target string (or to_string) far deeper in the graph. Then we have to keep track of the levels at which it is found and the reference to that node, and finally find the minimum level possible and then trace it from root.
For example, consider this conversion from -> zoom:
from
/ \
fram foom
/ \ / \
dram drom [zoom] food << To traverse upto this level is enough
... | ...
doom
|
[zoom]
Using BFS, we can simplify this process by a great deal. All we need to do is :
from string at level 0. Add this string to visitedSetOfStrings.visitedSetOfStrings.target string, stop further processing of nodes/strings. Otherwise continue to step 2.To make the path tracing easier, we can add extra information of parent string in each node.
class Solution {
//static int ans=Integer.MAX_VALUE;
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
HashMap<String,Integer> h=new HashMap<String,Integer>();
HashMap<String,Integer> h1=new HashMap<String,Integer>();
for(int i=0;i<wordList.size();i++)
{
h1.put(wordList.get(i),1);
}
int count=0;
Queue<String> q=new LinkedList<String>();
q.add(beginWord);
q.add("-1");
h.put(beginWord,1);
int ans=ladderLengthUtil(beginWord,endWord,wordList,h,count,q,h1);
return ans;
}
public int ladderLengthUtil(String beginWord, String endWord, List<String> wordList,HashMap<String,Integer> h,int count,Queue<String> q,HashMap<String,Integer> h1)
{
int ans=1;
while(!q.isEmpty())
{
String s=q.peek();
q.poll();
if(s.equals(endWord))
{
return ans;
}
else if(s.equals("-1"))
{
if(q.isEmpty())
{
break;
}
ans++;
q.add("-1");
}
else
{
for(int i=0;i<s.length();i++)
{
for(int j=0;j<26;j++)
{
char a=(char)('a'+j);
String s1=s.substring(0,i)+a+s.substring(i+1);
//System.out.println("s1 is "+s1);
if(h1.containsKey(s1)&&!h.containsKey(s1))
{
h.put(s1,1);
q.add(s1);
}
}
}
}
}
return 0;
}
}