Last Updated: 23 Jan, 2021

Word Ladder

Hard

Asked in companies

Solve now

Problem statement

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.

Solve now

Approaches

01 Approach

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.

Solve now

02 Approach

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.

Solve now

03 Approach

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.

Solve now