Last Updated: 21 Mar, 2021

Minimum Words Distance

Moderate

Asked in companies

Solve now

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”

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

Solve now

Approaches

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

Create ‘DIST’ as hashmap initialized to infinity.
Create ‘WAYS’ as hashmap initialized to 0.
Initialize ‘DIST[START]’ = 0, and ‘WAYS[START]’ = 1.
‘QUEUE’ = ‘[START]’.
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]’
Return ‘WAYS[END]’

Solve now