He didn't explained the question properly

#1

he didn’t told how to create the graph with single chracter difference as neighbour

#2

Hey,
To efficiently find the neighboring nodes for any given word we do some pre-processing on the words of the given wordList . The pre-processing involves replacing the letter of a word by a non-alphabet say, * .

2438×1549 51.7 KB

This pre-processing helps to form generic states to represent a single letter change.

For e.g. Dog ----> D*g <---- Dig

Both Dog and Dig map to the same intermediate or generic state D*g .

The preprocessing step helps us find out the generic one letter away nodes for any word of the word list and hence making it easier and quicker to get the adjacent nodes. Otherwise, for every word we will have to iterate over the entire word list and find words that differ by one letter. That would take a lot of time. This preprocessing step essentially builds the adjacency list first before beginning the breadth first search algorithm.

For eg. While doing BFS if we have to find the adjacent nodes for Dug we can first find all the generic states for Dug .

  1. Dug => *ug
  2. Dug => D*g
  3. Dug => Du*

The second transformation D*g could then be mapped to Dog or Dig , since all of them share the same generic state. Having a common generic transformation means two words are connected and differ by one letter.

#3

Hey @rkrrockstar89
I hope your doubt is resolved ,if its then please mark it as resolved :slight_smile:
If its not then let me know the issue.

#4

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.