Convert word A to B using a given dictionary - PrismoSkills
Problem: Given a dictionary of words and two words A and B, find the minimum path required to convert A to B.
Only one character can be changed at a time while going from A to B and every word thus formed must be a valid dictionary word.
Solution: We need to convert A to every possible dictionary word by changing one character at a time.
From these possible words, if any of the words is B, then a solution is found, else recursive check
is made starting from each of the new words formed above.
if the dictionary had only 2 words as 'log' and 'leg', then the hash-map would look like:
Once such a hash-map is there, then it becomes easy to find words in dictionary formed by changing just one character.
And then the DFS search can continue as usual to find the path.
Read full article from Convert word A to B using a given dictionary - PrismoSkills
Problem: Given a dictionary of words and two words A and B, find the minimum path required to convert A to B.
Only one character can be changed at a time while going from A to B and every word thus formed must be a valid dictionary word.
Solution: We need to convert A to every possible dictionary word by changing one character at a time.
From these possible words, if any of the words is B, then a solution is found, else recursive check
is made starting from each of the new words formed above.
if the dictionary had only 2 words as 'log' and 'leg', then the hash-map would look like:
"og0": ["log"] "lg1": ["log", "leg"] "lo2": ["log"] "eg0": ["leg"] "le2": ["leg"]
Once such a hash-map is there, then it becomes easy to find words in dictionary formed by changing just one character.
And then the DFS search can continue as usual to find the path.
Read full article from Convert word A to B using a given dictionary - PrismoSkills