Word Ladder
You are given two strings BEGIN and END and an array of strings DICT. Your task is to find the length of the shortest transformation sequence from BEGIN to END such that in every transformation you can change exactly one alphabet and the word formed after each transformation must exist in DICT.

Note:

1. If there is no possible path to change BEGIN to END then just return -1. 2. All the words have the same length and contain only lowercase english alphabets. 3. The beginning word i.e. BEGIN will always be different from the end word i.e. END (BEGIN != END).

Input format :

The first line of input contains an integer ‘T’ denoting the number of test cases. The first line of each test case contains a string BEGIN. The second line of each test case contains a string END. The third line of each test case contains a single integer N denoting the length of the DICT i.e. the array of strings. The fourth line of each test case contains N space-separated strings denoting the strings present in the DICT array.

Output format :

For each test case, print a single integer representing the length of the shortest transformation sequence from BEGIN to END. The output of each test case will be printed in a separate line.

Note:

You don’t have to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1

Question

Word Ladder

You are given two strings BEGIN and END and an array of strings DICT. Your task is to find the length of the shortest transformation sequence from BEGIN to END such that in every transformation you can change exactly one alphabet and the word formed after each transformation must exist in DICT.

Note:

1. If there is no possible path to change BEGIN to END then just return -1.
2. All the words have the same length and contain only lowercase english alphabets.
3. The beginning word i.e. BEGIN will always be different from the end word i.e. END (BEGIN != END).

Input format :

The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains a string BEGIN.

The second line of each test case contains a string END.

The third line of each test case contains a single integer N denoting the length of the DICT i.e. the array of strings.

The fourth line of each test case contains N space-separated strings denoting the strings present in the DICT array.

Output format :

For each test case, print a single integer representing the length of the shortest transformation sequence from BEGIN to END. 

The output of each test case will be printed in a separate line.

Note:

You don’t have to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= N<= 10^2
1 <= |S| <= 10^2

Where ‘T’ is the total number of test cases, ‘N’ denotes the length of the DICT array and |S| represents the length of each string.

Accepted Answer

Start from the given start word.
Push the word in the queue
Run a loop until the queue is empty
Traverse all words that adjacent (differ by one character) to it and push the word in a queue (for BFS)
Keep doing so until we find the target word or we have traversed all words.

Accepted Answer

Using BFS

The idea is to use BFS traversal of the graph because considering an edge between any two adjacent words(words that will have a difference of only one alphabet) after that you just have to find the shortest between the start word and the target word and that can be done using BFS.

Here is the algorithm:

As the BFS procedure goes start to form the "BEGIN " word, add it to the queue
“QUEUE”, and also declare a variable "COUNT" = 1 to store the answer.
Now till the QUEUE goes empty run a while loop i.e. pop each word from the QUEUE in the respective iterations.
- Inside this loop run a loop for the current size of the QUEUE and "check for the target word.
- If the current word becomes equal to "END" then just return the "COUNT".
- Else just iterate the word, check how many alphabets are different from the target word, store it in a variable say CHECK.
- If this "CHECK "variable becomes 1 then that means we have reached the "END" word and return "COUNT".
- Else just add the number which is adjacent to the word and add it to the "QUEUE”.
Now in the final statement if the function doesn't hit the return statement then that means there is no possible path so just return -1.

Space Complexity: OtherExplanation:

O(N * |S|), where ‘N’ denotes the length of the DICT and |S| is the length of each string.

We are using a queue to store all words.

Time Complexity: OtherExplanation:

O((N ^ 2) * |S|), where ‘N’ denotes the length of the DICT and |S| is the length of each string.

Since every word can be added to the queue, and each word needs to be compared with every word in the DICT. Each comparison takes O(|S|). Thus, the final time complexity is O((N ^ 2) * |S|).

Python (3.5)

'''

    Time Complexity: O((N ^ 2) * |S|)

    Space complexity: O(N * |S|)



    Where 'N' denotes the length of the DICT and |S| is the length of each string.

'''



def wordLadder(begin, end, arr):



    dict = {}



    for char in arr:

        dict[char] = True

    

    # Add the begin word.

    queue = [begin]



    # If the end word is not present in dict then just return -1.

    if end not in dict:

        return -1



    dept = 1

    while queue:

        dept += 1



        cur_len = len(queue)

        # Iterate through the queue.

        for _ in range(cur_len):

            cur_word = queue.pop(0)



            for i in range(len(cur_word)):

                # Check for the adjacent word.

                for char in 'abcdefghijklmnopqrstuvwxyz':

                    tmp = cur_word[:i]+char+cur_word[i+1:]

                    if (tmp in dict) and (tmp != cur_word):

                        queue.append(tmp)

                        dict.pop(tmp)



                    if tmp == end:

                        return dept

    

    # If it's not possible to form the word.

    return -1

Java (SE 1.8)

/*

    Time Complexity: O((N^2) * |S|)

    Space complexity: O(N * |S|)



    Where 'N' denotes the length of the DICT and |S| is the length of each string.

*/

import java.util.LinkedList;

import java.util.Queue;

import java.util.HashSet;

import java.util.ArrayList;



public class Solution {

    public static int wordLadder(String begin, String end, ArrayList < String > dict) {



        // If the end word is not present in dict then just return -1.

        if (dict.contains(end) == false) {

            return -1;

        }

        Queue < String > queue = new LinkedList < > ();

        int count = 1;



        // Add the begin word.

        queue.add(begin);

        HashSet < String > set = new HashSet < String > ();

        set.add(begin);



        while (queue.size() > 0) {

            count++;



            // Iterate through queue.

            for (int i = 0; i < queue.size(); i++) {



                String currentWord = queue.remove();

                if (currentWord.equals(end)) {

                    return count;

                }

                int check = 0;



                for (int z = 0; z < currentWord.length(); z++) {



                    if (currentWord.charAt(z) != end.charAt(z)) {

                        check++;

                    }

                }

                if (check == 1) {

                    return count;

                }



                // Check for the adjacent word.

                for (int j = 0; j < dict.size(); j++) {



                    int diff = 0;

                    for (int k = 0; k < currentWord.length(); k++) {



                        if (currentWord.charAt(k) != dict.get(j).charAt(k)) {

                            diff++;

                        }

                    }

                    if (diff == 1) {

                        if (set.contains(dict.get(j)) == false) {

                            queue.add(dict.get(j));

                            set.add(dict.get(j));

                        }

                    }

                }

            }

        }

        return -1;

    }

}

C++ (g++ 5.4)

/*

    Time Complexity: O((N ^ 2) * |S|)

    Space complexity: O(N * |S|)



    Where 'N' denotes the length of the DICT and |S| is the length of each string.

*/



#include

#include

#include 



int wordLadder(string begin, string end, vector < string > & dict) {

    // If the end word is not present in dict then just return -1.

    if (std::find(dict.begin(), dict.end(), end) == dict.end()) {

        return -1;

    }



    queue < string > queue;

    int count = 1;



    // Add the begin word.

    queue.push(begin);

    set < string > set;



    set.insert(begin);



    while (queue.size() > 0) {

        count++;

        // Iterate through the queue.

        for (int i = 0; i < queue.size(); i++) {

            string currentWord = queue.front();

            queue.pop();



            if (currentWord == end) {

                return count;

            }

            int check = 0;



            for (int z = 0; z < currentWord.size(); z++) {

                if (currentWord[z] != end[z]) {

                    check++;

                }

            }

            if (check == 1) {

                return count;

            }



            // Check for the adjacent word.

            for (int j = 0; j < dict.size(); j++) {

                int diff = 0;



                for (int k = 0; k < currentWord.size(); k++) {

                    if (currentWord[k] != dict[j][k]) {

                        diff++;

                    }

                }

                if (diff == 1) {

                    if (set.find(dict[j]) == set.end()) {

                        queue.push(dict[j]);

                        set.insert(dict[j]);

                    }

                }

            }

        }

    }

    // If it's not possible to form the word.

    return -1;

}

Accepted Answer

Using Trie

The idea is to use BFS traversal but along with that make use of trie data structure for storing the words of "DICT".

Here is the algorithm:

Create a class TRIE and insert all the words in the "DICT".
As the BFS procedure goes start from the “BEGIN” word, add it to the queue "QUEUE".
Here, we will also maintain a hashmap for storing the visited word.
Now till the "QUEUE" goes empty run a while loop i.e. pop each word from the "QUEUE" in the respective iterations.
- Here we will calculate all the possible permutations of the word that differ just by one character for this to generate all the possible permutations we use the function ALLPERMUTATIONS.
- In this function, we change a character one by one and generate all possible words and check whether it is present in the "DICT" or not if it is present we add it to the arraylist.
- Now add those words in the "QUEUE" which are not yet visited in the hashmap.
- We repeat the same procedure until the "QUEUE" goes empty.
Now if we encounter the target word i.e. END then just return from there with the minimum distance else return -1 finally.

Space Complexity: OtherExplanation:

O( N * (|S| * |S|) ), where ‘N’ denotes the length of the DICT and |S| is the length of each string of DICT.

Since for storing all permutations, we will have |S| * |S| space and that is for each iteration so total will (N * |S| * |S|).

Time Complexity: OtherExplanation:

O( N * (|S| * |S|) ), where ‘N’ denotes the length of the DICT and |S| is the length of each string of DICT.

Since every word can be added to the queue and we are checking all possible permutations for each word so total complexity for generating permutations will be O(|S| * |S|).

C++ (g++ 5.4)

/*

    Time Complexity:  O(N * (|S| * |S|))

    Space complexity: O(N * (|S| * |S|))



    Where 'N' denotes the length of the DICT and |S| is the length of each string.

*/



#include 



#include 



class TrieNode {

    public:

        unordered_map < char, TrieNode * > children;



    // For getting end of word.

    bool endOfWord;

    char ch;



    TrieNode(char ch) {

        this -> ch = ch;

        endOfWord = false;

        children[ch] = NULL;

    }

};



// Function to insert words of dict.

void insertWord(TrieNode * root, string & word, int i = 0) {

    if (i == word.size()) {

        root -> endOfWord = true;

        return;

    }



    if (root -> children[word[i]] == NULL) {

        root -> children[word[i]] = new TrieNode(word[i]);

    }



    insertWord(root -> children[word[i]], word, i + 1);

}



void allPermutations(TrieNode * root, string & str, vector < string > & all, string curr = "", bool changed = false, unsigned int i = 0) {

    // We can not get any string.

    if (root == NULL) {

        return;

    }



    // Finaly we got a string but will store only when it is a valid word from dictionary.

    if (curr.size() == str.size()) {

        if (root -> endOfWord) {

            all.push_back(curr);

        }

        return;

    }



    // Check further in trie.

    for (auto x: root -> children) {

        curr.push_back(x.first);



        if (x.first == str[i]) {

            allPermutations(x.second, str, all, curr, changed, i + 1);

        } else if (!changed) {

            allPermutations(x.second, str, all, curr, !changed, i + 1);

        }



        // BackTrack.

        curr.pop_back();

    }

}



int wordLadder(string & begin, string & end, vector < string > & dict) {

    // Make a Trie.

    TrieNode * root = new TrieNode('\0');



    // Insert all word from dictionary into trie.

    for (string x: dict) {

        insertWord(root, x);

    }



    // Queue for BFS.

    queue < string > q;

    q.push(begin);



    // Check for visited words.

    unordered_map < string, int > visited;

    visited[begin] = 1;



    // Start BFS.

    while (q.size() > 0) {

        string str = q.front();

        q.pop();



        // If str is the target then return it.

        if (str == end) {

            return visited[str];

        }



        // Store all the permutations.

        vector < string > allPossible;

        allPermutations(root, str, allPossible);



        // Push into queue if they are not visited yet.

        for (string x: allPossible) {

            if (visited.count(x) == 0) {

                q.push(x);

                visited[x] = visited[str] + 1;

            }

        }

    }

    return -1;

}

Java (SE 1.8)

/*

    Time Complexity:  O(N * (|S| * |S|))

    Space complexity: O(N * (|S| * |S|))



    Where 'N' denotes the length of the DICT and |S| is the length of each string.

*/



import java.util.Queue;

import java.util.HashMap;

import java.util.ArrayList;

import java.util.LinkedList;



class Trie {



    public HashMap < Character, Trie > child;



    public boolean tail;

    char ch;



    Trie(char ch) {

        this.ch = ch;

        tail = false;

        child = new HashMap < Character, Trie > ();

    }

}



public class Solution {



    // Function to insert words of dict.

    private static void insertWord(Trie root, String word, int i) {



        if (i == word.length()) {

            root.tail = true;

            return;

        }



        if (root.child.get(word.charAt(i)) == null) {

            root.child.put(word.charAt(i), new Trie(word.charAt(i)));

        }



        insertWord(root.child.get(word.charAt(i)), word, i + 1);

    }



    private static void allPermutations(Trie root, String str, ArrayList < String > all, StringBuilder sb, boolean flag, int i) {



        // If root is null then just return.

        if (root == null) {

            return;

        }

        // If the string obtained is present in dict then add.

        if (sb.length() == str.length()) {



            if (root.tail) {

                all.add(sb.toString());

            }

            return;

        }

        // Check further in trie.

        for (HashMap.Entry < Character, Trie > map: root.child.entrySet()) {



            sb.append(map.getKey());



            if (map.getKey() == str.charAt(i)) {



                allPermutations(map.getValue(), str, all, sb, flag, i + 1);

            } else if (!flag) {



                allPermutations(map.getValue(), str, all, sb, !flag, i + 1);

            }

            // Delete.

            sb.deleteCharAt(sb.length() - 1);

        }

    }



    public static int wordLadder(String begin, String end, ArrayList < String > dict) {



        Trie root = new Trie('\0');



        // Add all the words in the dict to trie declared.

        for (String x: dict) {



            insertWord(root, x, 0);

        }



        // Queue for BFS.

        Queue < String > queue = new LinkedList < String > ();



        queue.add(begin);



        // Check for visited words.

        HashMap < String, Integer > check = new HashMap < String, Integer > ();



        check.put(begin, 1);



        // Start BFS.

        while (queue.size() > 0) {



            String str = queue.remove();



            // If str is the target then return it.

            if (str.equals(end)) {

                return check.get(str);

            }



            // Store all the permutations.

            ArrayList < String > all = new ArrayList < String > ();



            StringBuilder sb = new StringBuilder();



            allPermutations(root, str, all, sb, false, 0);



            // Push into queue if they are not visited yet.

            for (String st: all) {



                if (check.containsKey(st) == false) {

                    queue.add(st);

                    check.put(st, check.get(str) + 1);

                }

            }



        }

        return -1;

    }

}

Python (3.5)

'''

    Time Complexity:  O(N * (|S| * |S|))

    Space complexity: O(N * (|S| * |S|))



    Where 'N' denotes the length of the DICT and |S| is the length of each string.

'''



from collections import deque



class TrieNode:

    def __init__(self, char):

        self.char = char

        # For getting end of word.

        self.endOfWord = False

        self.children = {}

        

# Function to insert words of dict.

def insertWord(root, word):

    curr = root

    for char in word:

        if char not in curr.children:

            curr.children[char] = TrieNode(char)

        curr = curr.children[char]

    curr.endOfWord = True

    

def allPermutations(root, word, allPossible, changed=False, curr='', i=0):

    

    # We can not get any string.

    if root is None:

        return

    

    # Finaly we got a string but will store only when it is a valid word from dictionary.

    if len(curr) == len(word):

        if root.endOfWord:

            allPossible.append(curr)

        return

    

    # Check further in trie.

    for x in root.children:

        if x == word[i]:

            allPermutations(root.children.get(x, None), word, allPossible, changed, curr+x, i+1)

        elif not changed:

            allPermutations(root.children.get(x, None), word, allPossible, not changed, curr+x, i+1)





def wordLadder(begin, end, wordDict):

    

    # Make a Trie.

    root = TrieNode('/')

    

    # Insert all word from dictionary into trie.

    for word in wordDict:

        insertWord(root, word)

    

    # Queue for BFS.

    q = deque()

    q.append(begin)

    

    # Check for visited words.

    visited = {}

    visited[begin] = 1

    

    # Start BFS.

    while len(q) > 0:

        

        # If str is the target then return it.

        currWord = q.popleft()

        

        # If str is the target then return it.

        if currWord == end:

            return visited[currWord]

        

        # Store all the permutations.

        allPossible = []

        allPermutations(root, currWord, allPossible)

        

        # Push into queue if they are not visited yet.

        for word in allPossible:

            if word not in visited:

                q.append(word)

                visited[word] = visited[currWord] + 1

                

    return -1

Accepted Answer

Using Bi-Directional BFS

The idea is to use BFS traversal but doing it from both "END"s, that is from the target "END" word and "BEGIN" word, we are doing this because we can calculate the distance in half the time rather than compared to single BFS as in the previous approach-

Here is the algorithm:

Here, we will do the similar thing as in the previous approach just we will maintain two hash sets, one for the "BEGIN" word and another for the "END" word.
Here, we will also maintain a HashSet for storing the visited words from both sides.
We will start BFS from both directions by adding "BEGIN" to the HashSet one and "END" to the second HashSet .
Similarly, run a while loop while both the hash sets go empty.
- If the beginner HashSet size is bigger than the second HashSet then just swap those.
- Now iterate through the "BEGIN" HashSet and check for each word.
- Now iterate through the word and check whether its neighbor exists in the original DICT.
- You will check by putting every letter from ‘a’ to ‘z’ and check that it is present in DICT or not.
- But if the word becomes equal to the target word then just return the length.
- If the function doesn't return on the above that means there is no path so finally return -1.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ denotes the length of the DICT.

since we are using a hashset to store all words.

Time Complexity: OtherExplanation:

O(N * |S|*26), where ‘N’ denotes the length of the DICT and |S| is the length of each string of DICT.

Since every word can be added to the queue and we are checking the neighbors (by iterating over the word to find the word that differs just by one alphabet) for each word so total complexity will be O(N*|S|).

C++ (g++ 5.4)

/*

    Time Complexity: O(N * |S| * 26)

    Space complexity: O(N)



    Where 'N' denotes the length of the DICT and |S| is the length of each string.

*/



#include



int wordLadder(string & begin, string & end, vector < string > & dict) {



    int depth = 1;

    unordered_set < string > set(dict.begin(), dict.end());



    // If the end word is not present then just return form here.

    if (set.count(end) == 0) return -1;



    unordered_set < string > beginSet, endSet;

    int len = beginSet.size();

    unordered_set < string > visited;

    beginSet.insert(begin);

    endSet.insert(end);



    // Start the BSF from both sides.

    while (!beginSet.empty() && !endSet.empty()) {

        if (beginSet.size() > endSet.size()) {

            unordered_set < string > temp = beginSet;

            beginSet = endSet;

            endSet = temp;

        }

        unordered_set < string > temp;



        // Check for each word in the begin set.

        for (string word: beginSet) {

            // For finding the adjacent words.

            for (int i = 0; i < word.size(); i++) {

                /* 

                	Make a new word by adding chararcters and

                    check if it is present in dict.

                */

                for (char c = 'a'; c <= 'z'; c++) {

                    char old = word[i];

                    word[i] = c;

                    if (endSet.count(word) != 0) {

                        return depth + 1;

                    }

                    if (visited.count(word) == 0 && set.count(word) != 0) {

                        temp.insert(word);

                        visited.insert(word);

                    }

                    word[i] = old;

                }

            }

        }

        beginSet = temp;

        depth++;

    }

    return -1;

}

Java (SE 1.8)

/*

    Time Complexity: O(N * |S| * 26)

    Space complexity: O(N)



    Where 'N' denotes the length of the DICT and |S| is the length of each string.

*/



import java.util.HashSet;

import java.util.Set;

import java.util.ArrayList;



public class Solution {



    public static int wordLadder(String begin, String end, ArrayList < String > dict) {



        // If the end word is not present then just return form here.

        if (dict.contains(end) == false) {

            return -1;

        }

        Set  dictSet = new HashSet <> (dict);

        Set  beginSet = new HashSet <> ();

        Set  endSet = new HashSet <> ();

        beginSet.add(begin);

        endSet.add(end);



        int step = 1;

        Set  visited = new HashSet <> ();



        // Start the BSF from both sides.

        while (beginSet.isEmpty() == false && endSet.isEmpty() == false) {



            if (beginSet.size() > endSet.size()) {

                Set  set = beginSet;

                beginSet = endSet;

                endSet = set;

            }

            Set  temp = new HashSet < > ();



            // Check for each word in the begin hashset.

            for (String word: beginSet) {



                char[] chs = word.toCharArray();

                // For finding the adjacent words.

                for (int i = 0; i < chs.length; i++) {



                    /* 

                    	Make a new word by adding chararcters and

                        check if it is present in dict.

                    */

                    for (char c = 'a'; c <= 'z'; c++) {



                        char old = chs[i];

                        chs[i] = c;

                        String target = String.valueOf(chs);

                        if (endSet.contains(target)) {



                            return step + 1;

                        }

                        if (visited.contains(target) == false && dictSet.contains(target)) {



                            temp.add(target);

                            visited.add(target);

                        }

                        chs[i] = old;

                    }

                }

            }

            beginSet = temp;

            step++;

        }



        return -1;

    }

}

Python (3.5)

'''

    Time Complexity: O(N * |S| * 26)

    Space complexity: O(N)



    Where 'N' denotes the length of the DICT and |S| is the length of each string.

'''



from string import ascii_lowercase



def wordLadder(begin, end, dict):



    # If the end word is not present then just return form here.

    if end not in dict: return -1

    

    wordSet = set(dict)



    '''

         Function Make a new word by adding chararcters 

         and check if it is present in dict.

    '''

    def nextWords(word, seen): 

        for i in range(len(word)):

            for c in ascii_lowercase:

                nextWord = word[:i] + c + word[i+1:]

                if nextWord in wordSet and nextWord not in seen:

                    yield nextWord

        

    beginSet, endSet = set([begin]), set([end])

    beginSeen, endSeen = set([begin]), set([end])

    step = 1



    # Start the BSF from both sides.

    while len(beginSet) > 0 and len(endSet) > 0:

        tempSet = beginSet

        beginSet = set()

        for word in tempSet:

            # Check for each word in the begin in set.

            for nextWord in nextWords(word, beginSeen):

                if nextWord in endSet: 

                    return step + 1                    

                beginSet.add(nextWord)

                beginSeen.add(nextWord)

        step += 1

        # work on each direction in turn

        beginSet, endSet = endSet, beginSet

        beginSeen, endSeen = endSeen, beginSeen

    

    return -1

You are given two strings BEGIN and END and an array of strings DICT. Your task is to find the length of the shortest transformation sequence from BEGIN to END such that in every transformation you can change exactly one alphabet and the word formed after each transformation must exist in DICT.

Note:

Input format :

Output format :

Note:

Constraints:

Top Tower Research Capital LLC SDE-2 interview questions & answers

Popular interview questions of SDE-2