Word Ladder

Hard
0/120
Average time to solve is 10m
64 upvotes
Asked in companies
OlaSalesforceMakeMyTrip

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).
Detailed explanation ( Input/output format, Notes, Images )
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.
Hint

Try to think in terms of graph, how you can move from one word to another?

Approaches (3)
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: 

  

  1. 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.
  2. 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”.
  3. 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.
Time Complexity

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|).

Space Complexity

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.

Code Solution
(100% EXP penalty)
Word Ladder
Full screen
Console