Intuition:

• BFS Level/Frontier order to find shortest path
• Potential neighbors are the all letter permutations for each index
  • Add to queue if they are in wordList and have not been visited!

Strategy:

• Level Order traversal
• convert wordList to wordSet (for faster lookup)
• For neighbor generation, change only 1 character (instead of copying word). Also python strings are immutable
  • Use backtracking to generate the permutations of the 1-letter-off words
  • PathArr = list(path) # “ABC” —> [A,B,C]
  • pathArr[i] = letter
  • ‘’.join(PathArr) # [A,B,C] —> “ABC"
• From the potential neighbors, wordSet, and seenSet, find the unseen words and add them to queue.
• Seen set (aka visited set) is created so we don’t repeat processing the node

Example Walk-through

WordLadder.pdf

WordLadder.pptx

Algorithm

def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        # generate list of neighbors
        def getPotentialNeighbors(path:str)-> List[str]:
            neighborList=[]
            pathArr = list(path)
            
            for i in range(len(path)):                
                
                for letter in alphabet:                                    
                    tmp = path[i]  
                    
                    pathArr[i] = letter
                    neighborList.append(''.join(pathArr))
                    
                    pathArr[i] = tmp
            
            return neighborList
        
        seen = set()
        wordSet = set()
        level = 0
        alphabet = "abcdefghijklmnopqrstuvwxyz"
        
        for word in wordList:
            wordSet.add(word)            
        
        q = []        
        q.append(beginWord)
        
        if endWord not in wordList:
            return 0
        while len(q)>0:            
            
            levelSize = len(q)
            level += 1
            
						# LevelOrder: 
						#   Only loop through current level's nodes, 
						#   while adding more to the back of queue
            for i in range(levelSize):  
                cur = q.pop(0)
                if cur == endWord:
                    return level
                
                neighbors = getPotentialNeighbors(cur)
                for neigh in neighbors:
                    if neigh in wordSet and neigh not in seen:
                        q.append(neigh)
                        seen.add(neigh)

        return 0