Minimum Words Distance

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
7 upvotes
Asked in companies
VisaSalesforceUber

Problem statement

You are given two words START and END and a dictionary of words WORDDIC. All the words in WORDDIC are unique. START and END may or may not be present in WORDDIC.

You can make a transition from one word to another if both the words are present in WORDDIC and both words have exactly one letter differ. Your task is to find the number of minimum distance paths from START to END using the transitions explained above.

The distance between two words is the number of transitions used to go from one word to another.

For example:

START = “cow” END = “mot”
WORDDIC = [“cow”, “mow”, “cot”, “mot”]
Here answer is 2 there are two paths of distance 2 ,
“cow” -> “mow” -> “mot” 
“cow” -> “cot”  -> “mot”
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer 'T' denoting the number of test cases to run. Then the test case follows.

The first line of each test case contains two space-separated words START and END. 

The second line of each test case contains a single integer ‘N’, denoting the length of WORDDIC.

The third line of each test case contains ‘N’ space-separated words, denoting the elements of WORDDIC.
Output Format: 
For each test case print a single integer denoting the number of paths from START to END.

Output for each test case is printed in a separate line.
Note: 
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= N <= 5000 
1 <= len(WORD) <= 10

Where ‘N’ is the length of WORDDIC, len(WORD) is the length of START, END, and words in WORDDIC. All the words are lower case English words.

Time Limit: 1 sec
Sample Input 1:
2
ab xy
5
xb az eb ab xy
hat cat 
5
hat let  mat set gat
Sample Output 1:
1
0
Explanation of Sample Input 1:
For the first test case, there is only one path from “ab” to “xy”,   “ab” -> “xb” -> “xy”.

For the second test case, END is not in WORDDIC.
Sample Input 2:
2 
a c
7
a b c d e f g
ninjas kinjas
2 
ninjas kinjas
Sample Output 2:
1
1
Explanation of Sample Input 2:
For the first test case, there is only one path from “a” to “c”,   “a” -> “c”.

For the second test case, there is only one word change from “ninjas” to “kinjas”.
Hint

Can we use a breadth-first search to find the shortest path length from START to END? And the number of such paths? 

Approaches (1)
BFS Approach

We will maintain two hashmaps DIST and WAYS. DIST stores the minimum distance of a word from START and ways stores the number of minimum paths from the START to the current word. To make a transition we will iterate over all positions and try all the possible characters at this position. If the new word is present in the dictionary then make the transition.

 

The algorithm will be:

  1. Create ‘DIST’ as hashmap initialized to infinity.
  2. Create ‘WAYS’ as hashmap initialized to 0.
  3. Initialize ‘DIST[START]’ = 0, and ‘WAYS[START]’ = 1.
  4. ‘QUEUE’ = ‘[START]’.
  5. While (size of QUEUE is not equal to 0)
    • Initialize ‘WORD’ to the front element of the ‘QUEUE’.
    • Now for each ‘i’ from 0 to ‘N’ - 1:
      • For CHAR in ‘a’ to ‘z’
        • ‘NEWWORD’ = ‘WORD’
        • ‘NEWWORD[i]’ = ‘CHAR’
        • If ‘NEWWORD’ in ‘WORDDICT’
          • If ‘DIST[NEWWORD]’ == infinity
            • ‘DIST[NEWWORD]’ = ‘DIST[WORD]’ + 1
            • ‘QUEUE.append(NEWWORD)’
          • If ‘DIST[NEWWORD]’ == ‘DIST[WORD]’ + 1
            • ‘WAYS[NEWWORD]’ += ‘WAYS[WORD]’
  6. Return ‘WAYS[END]’
Time Complexity

O(N * WL * C) where N is the size of WORDDIC, WL is the length of words and C is the number of possible characters which is 26 in our case. 

 

We are visiting a word once and for each possible position we are trying all the possible characters. Hence our overall complexity will be O(N * WL * C).

Space Complexity

O(N) where N is the size of WORDDIC.

 

The space required to store DIST and WAYS dictionary if of order O(N). Thus, overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Minimum Words Distance
Full screen
Console