Path between Two Input Words in a Dictionary

Give a dictionary, write a method to check if there is a path from input word to target word, provided only one character can be changed at each step.

Example


Input:  cat
target: dog 
Output: true
Path:   cat -> cot -> cog -> dog

Refer to the Use Me section for the necessary variable and method declarations.

Need a hand? Try out these hints, one at a time.

Quick hint to get things rolling

Starting from the input word, check for potential candidates and push then into the path stack by marking their visited property to true. Before jumping to the solution, get yourself familiar with the helper functions from the Use Me section.

Final hint! You should be able to code the problem on viewing this.

Check for the available Apis from the Use Me section which are necessary for solving this problem. The key here is to recursively verify the validity of potential words to reach to the target word. The steps are as follows.

1. If the input word is equal to the target word, return true.

2. Populate all the potential candidates to a queue by making use of the potentialCandidates api from the Use Me section.

3. Loop through all the words in the queue. If the visited property of a word is null, then make a recursive call to check for its chain, if the chain exists, push the word in the path stack.

4. Else, if the chain does not exist, mark the visited property of that word to true.

//Assume target word is already set, write an algorithm to check for chain from input1 to target word.
private boolean checkForChain(String input1)
{



}

This Coding Interview Question is available with an answer in the following programming languages :

Java

Python

Path between Two Input Words in a Dictionary

Quick hint to get things rolling

Final hint! You should be able to code the problem on viewing this.

The interview prep tool you'll fall in love with!

This Coding Interview Question is available with an answer in the following programming languages :