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.
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.
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) { }
C
Java
Python