Algorithm to transform one word to another through valid words

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

Create a graph with each node representing word in the dictionary. Add an edge between two word nodes, if their corresponding words are at edit distance of 1. Then minimum number of transformations required would length of shortest path between source node and destination node.

Answer 4

You could simply use recursive back-tracking but this is far from the most optimal solution.

# Given two words of equal length that are in a dictionary, write a method to transform one word into another word by changing only
# one letter at a time.  The new word you get in each step must be in the
# dictionary.

# def transform(english_words, start, end):

# transform(english_words, 'damp', 'like')
# ['damp', 'lamp', 'limp', 'lime', 'like']
# ['damp', 'camp', 'came', 'lame', 'lime', 'like']


def is_diff_one(str1, str2):
    if len(str1) != len(str2):
        return False

    count = 0
    for i in range(0, len(str1)):
        if str1[i] != str2[i]:
            count = count + 1

    if count == 1:
        return True

    return False


potential_ans = []


def transform(english_words, start, end, count):
    global potential_ans
    if count == 0:
        count = count + 1
        potential_ans = [start]

    if start == end:
        print potential_ans
        return potential_ans

    for w in english_words:
        if is_diff_one(w, start) and w not in potential_ans:
            potential_ans.append(w)
            transform(english_words, w, end, count)
            potential_ans[:-1]

    return None


english_words = set(['damp', 'camp', 'came', 'lame', 'lime', 'like'])
transform(english_words, 'damp', 'lame', 0)

Answer 5

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.

Answer 6

@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 :

1. Start with from string at level 0. Add this string to visitedSetOfStrings.
2. Add non-visited valid strings to next level which are at edit distance +1 from the strings of current level.
3. Add all these strings to visitedSetOfStrings.
4. If this set contains the 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.

Answer 7

This is C# code to solve the problem using BFS:

//use a hash set for a fast check if a word is already in the dictionary
    static HashSet<string> Dictionary = new HashSet<string>();
    //dictionary used to find the parent in every node in the graph and to avoid traversing an already traversed node
    static Dictionary<string, string> parents = new Dictionary<string, string>();

    public static List<string> FindPath(List<string> input, string start, string end)
    {
        char[] allcharacters = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};

        foreach (string s in input)
            Dictionary.Add(s);
        List<string> currentFrontier = new List<string>();
        List<string> nextFrontier = new List<string>();
        currentFrontier.Add(start);
        while (currentFrontier.Count > 0)
        {
            foreach (string s in currentFrontier)
            {
                for (int i = 0; i < s.Length; i++)
                {
                    foreach (char c in allcharacters)
                    {
                        StringBuilder newWordBuilder = new StringBuilder(s);
                        newWordBuilder[i] = c;
                        string newWord = newWordBuilder.ToString();
                        if (Dictionary.Contains(newWord))
                        {
                            //avoid traversing a previously traversed node
                            if (!parents.Keys.Contains(newWord))
                            {
                                parents.Add(newWord.ToString(), s);
                                nextFrontier.Add(newWord);
                            }

                        }
                        if (newWord.ToString() == end)
                        {
                            return ExtractPath(start, end);

                        }
                    }
                }
            }
            currentFrontier.Clear();
            currentFrontier.Concat(nextFrontier);
            nextFrontier.Clear();
        }
        throw new ArgumentException("The given dictionary cannot be used to get a path from start to end");
    }

    private static List<string> ExtractPath(string start,string end)
    {
        List<string> path = new List<string>();
        string current = end;
        path.Add(end);
        while (current != start)
        {
            current = parents[current];
            path.Add(current);
        }
         path.Reverse();
         return path;
    }

Answer 8

I don't think we need graph or some other complicated data structure. My idea is to load the dictionary as a HashSet and use contains() method to find out if the word exists in the dictionary or not.

Please, check this pseudocode to see my idea:

Two words are given: START and STOP. 
//List is our "way" from words START to STOP, so, we add the original word to it first.
    list.add(START);
//Finish to change the word when START equals STOP.
    while(!START.equals(STOP))
//Change each letter at START to the letter to STOP one by one and check if such word exists.
    for (int i = 0, i<STOP.length, i++){
        char temp = START[i];
        START[i] = STOP[i];
//If the word exists add a new word to the list of results. 
//And change another letter in the new word with the next pass of the loop.
        if dictionary.contains(START)
           list.add(START)
//If the word doesn't exist, leave it like it was and try to change another letter with the next pass of the loop.
        else START[i] = temp;}
    return list;

As I understand my code should work like that:

Input: DAMP, LIKE

Output: DAMP, LAMP, LIMP, LIME, LIKE

Input: BACK, PICK

Output: BACK, PACK, PICK

Answer 9

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;    
    }
}

Answer 10

This is clearly a permutation problem. Using a graph is overkill. The problem statment is missing one important constraint; that you can change each position only once. This then makes it implicit that the solution is within 4 steps. Now all that needs to be decided is the sequence of the replace operations:

Operation1 = change "H" to "T"
Operation2 = change "E" to "A"
Operation3 = change "A" to "I"
Operation4 = change "D to "L"

The solution, the sequence of operations, is some permutation of the string "1234", where each digit represents the position of the character being replaced. e.g. "3124" indicates that first we apply operation3, then operation1, then operation2, then operation 4. At each step, if resulting word is not in dictionary, skip to next permutation. Reasonably trivial. Code anyone?