Make delicious recipes!

Convert word A to B using a given dictionary



Problem: Given a dictionary of words and two words A and B, find the minimum path required to convert A to B.
Only one character can be changed at a time while going from A to B and every word thus formed must be a valid dictionary word.

Example:
If dictionary = {
		"cat", "rat", "hat", "sag", "bag", "bug", "dog", "hog", "hot", "dot", 
		"rot", "lot", "log", "cry", "pry", "fry", "fat", "fog", "pot", "fat"
	}
A = "cat",
B = "dog",
then shortest path from A to B should be printed as:
cat->hat->hot->dot->dog

Note: There may be longer paths like cat->rat->fat->hat->hot->dot->dog,
but those are not required to be printed.


Solution: We need to convert A to every possible dictionary word by changing one character at a time.
From these possible words, if any of the words is B, then a solution is found, else recursive check
is made starting from each of the new words formed above.

This approach works fine except for one problem.
How to find all the dictionary words which can be formed by changing just one character in A?
This is solved by creating a hash-map of {string: list of words}.
They keys of this hash-map are formed by omitting characters one-by-one from
all the words in the dictionary and appending the index of the omitted character.

For example: if the dictionary had only 2 words as 'log' and 'leg', then the hash-map would look like:
"og0": ["log"]
"lg1": ["log", "leg"]
"lo2": ["log"]
"eg0": ["leg"]
"le2": ["leg"]


Once such a hash-map is there, then it becomes easy to find words in dictionary formed by changing just one character.
And then the DFS search can continue as usual to find the path.


Code in Java:

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map.Entry;


public class ConvertWordUsingDictionary 
{

    static String dictionary [] = {
        "cat", "rat", "hat", "sag", "bag", "bug", "dog", "hog", "hot", "dot", 
        "rot", "lot", "log", "cry", "pry", "fry", "fat", "fog", "pot", "pie"
    };
    
    
    // Map whose key is (word - a character) + index-of-omitted-character
    // and whose value is list of words having the same key
    static HashMap <String, ArrayList<String>> smallerWordsMap = new HashMap <String, ArrayList<String>> ();
    
    
    // Map to store minimum path from word 'k' to final word 'b'
    static HashMap<String, ArrayList<String>> wordToPathMap = new HashMap<String, ArrayList<String>> ();
    
    
    // Set to mark the words already visited by the recursive function
    static HashSet<String> visitedWords = new HashSet<String> ();
    
    
    // function to test the algorithm.
    public static void main(String[] args) 
    {
        String a = "cat";
        String b = "dog";
        
        createSmallerWordMap ();
        ArrayList<String> path = convertWord (a,b);
        printPath (a,path);
    }


    // For every word, takes out one character, forms a word with the remaining characters
    // and forms a key by concatenating this smaller word with index of smaller character.
    static void createSmallerWordMap() 
    {
        for (String word : dictionary)
        {
            for (int i=0; i<word.length(); i++)
            {
                // form a smaller word by omitting a character
                // index of omitted character is appended to the end of this smaller word.
                String smallerWord = 
                        word.substring(0, i) + 
                        word.substring(i+1, word.length()) +
                        i;
                
                // Use this smallerWord as a key in the hash-map
                // Value for this key is the list of words from which
                // this smaller word was formed.
                // Example: 'log' and 'leg' would both form a key 'lg1' when char at index 1 is omitted 
                ArrayList<String> list = smallerWordsMap.get(smallerWord);
                if (list == null)
                {
                    list = new ArrayList<String> ();
                    smallerWordsMap.put(smallerWord, list);
                }
                list.add(word);
            }
        }
        printSmallerWordMap();
    }
    
    
    // Main function which uses the smaller-Word-Map created above to find
    // the shortest path from a to b
    static ArrayList <String> convertWord (String a, String b) 
    {
        // If a path has been found already, return that
        ArrayList<String> existingPath = wordToPathMap.get(a);
        if (existingPath != null && existingPath.size() > 0)
            return existingPath;
        
        // Do not visit same word again.
        // This is used when recursion forms a cycle for example from rat->cat->rat->cat...
        // The wordToPathMap does not help here because there is yet no path for these words.
        if (visitedWords.contains(a))
            return null;
        visitedWords.add(a);
        
        
        System.out.println("Checking "+ a + "->" + b);
        
        ArrayList <String> minPath  = new ArrayList<String>();
        
        for (int i=0; i<a.length(); i++)
        {
            String smallerWord = 
                    a.substring(0, i) + 
                    a.substring(i+1, a.length()) +
                    i;
            
            ArrayList<String> list = smallerWordsMap.get(smallerWord);
            for (String word: list)
            {
                if (word.equals(a))
                    continue;
                
                if (word.equals(b)) // match found
                {
                    ArrayList <String> currPath = new ArrayList<String>();
                    currPath.add(word);
                    wordToPathMap.put(word, currPath);
                    return currPath;
                }
                
                ArrayList <String> fwdPath = convertWord(word, b); // recursive search
                
                if (fwdPath != null && fwdPath.size() > 0)
                {
                    if (minPath.size()==0 || minPath.size() > 1 + fwdPath.size())
                    {
                        minPath.clear();
                        minPath.add(word);
                        minPath.addAll(fwdPath);
                    }
                }
            }
        }
        
        wordToPathMap.put(a, minPath);
        return minPath;
    }

    
    /****************** Debug Utilities *********************/
    static void printPath(String a, ArrayList<String> path) 
    {
        System.out.println ();
        if (path == null || path.size() == 0)
        {
            System.out.println ("No path exists");
            return;
        }
        System.out.print(a);
        for (String w : path)
            System.out.print("->" + w);
    }
    

    static void printSmallerWordMap() 
    {
        Iterator<Entry<String, ArrayList<String>>> itr = smallerWordsMap.entrySet().iterator();
        while (itr.hasNext())
        {
            Entry<String, ArrayList<String>> e = itr.next();
            String smallerWord = e.getKey();
            ArrayList<String> list = e.getValue();
            System.out.print(smallerWord + ": ");
            for (String word: list)
                System.out.print(word+",");
            System.out.println();
        }
        System.out.println();
    }
    
}




Example executions:


Smaller Words Map: 
py1: pry,
ha2: hat,
fo2: fog,
cy1: cry,
ot0: hot,dot,rot,lot,pot,
ca2: cat,
do2: dog,dot,
ie0: pie,
ry0: cry,pry,fry,
po2: pot,
og0: dog,hog,log,fog,
ba2: bag,
lt1: lot,
at0: cat,rat,hat,fat,
hg1: hog,
ht1: hat,hot,
dg1: dog,
ag0: sag,bag,
lo2: lot,log,
cr2: cry,
rt1: rat,rot,
ct1: cat,
ro2: rot,
fg1: fog,
fy1: fry,
fr2: fry,
lg1: log,
ra2: rat,
pr2: pry,
dt1: dot,
pe1: pie,
bg1: bag,bug,
ft1: fat,
sa2: sag,
pi2: pie,
fa2: fat,
bu2: bug,
pt1: pot,
ug0: bug,
sg1: sag,
ho2: hog,hot,

recursive checking:
Checking cat->dog
Checking rat->dog
Checking hat->dog
Checking fat->dog
Checking hot->dog
Checking dot->dog
Checking rot->dog
Checking lot->dog
Checking pot->dog
Checking log->dog
Checking hog->dog

result:
cat->hat->hot->dot->dog


Order analysis:
For word 'A' of length 'm', the number of keys generated is also 'm'
If dictionary size for words of length 'm' is 'n', then smallerWordMap will have entries to the order of O(mn)

If A and B are at two opposite ends of the dictionary words, then the recursion will test all the O(mn) combinations.
Thus, order complexity of this algorithm is O(mn)





Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal