Easy to understand Python Solution (BFS+DFS)


#1
import sys
sys.setrecursionlimit(10**6)
from collections import defaultdict, deque
class Solution:
    # @param start : string
    # @param end : string
    # @param dictV : list of strings
    # @return a list of list of strings
    def __init__(self):
        self.ans = []
    def bfs(self, start, dictV, vis, adjacency):
        queue = deque()
        queue.append([start, 1])
        vis[start] = 1
        while queue:
            word, l = queue.popleft()
            for i in range(len(word)):
                for replace in "abcdefghijklmnopqrstuvwxyz":
                    if replace != word[i]:
                        newWord = ("" if i==0 else word[:i]) + replace + ("" if i+1==len(word) else word[i+1:])
                        if newWord in dictV:
                            if newWord not in vis:
                                vis[newWord] = l+1
                                queue.append([newWord, l+1])
                                adjacency[word].append(newWord)
                            elif vis[newWord] == vis[word] + 1:
                                adjacency[word].append(newWord)
            
    def dfs(self, start, end, adjacency, soFar):
        if start == end:
            self.ans.append(soFar[:])
            return
        for neigh in adjacency[start]:
            soFar.append(neigh)
            self.dfs(neigh, end, adjacency, soFar)
            soFar.pop()
            

    
    def findLadders(self, start, end, dictV):
        if end not in dictV:
            return []
        vis = {}
        adjacency = defaultdict(list)
        self.bfs(start, set(dictV), vis, adjacency)
        self.dfs(start, end, adjacency, [start])
        return self.ans