Python BFS + DFS approach


#1
res = []
mini = 0
def dfs(curr,end,adj,array,visited,depth):
    global mini, res
    if depth==mini:
        if curr == end:
            res.append(list(array))
        return
    
    for i in range(len(curr)):
        string = curr[:i]+"_"+curr[i+1:]
        for j in adj[string]:
            if visited[j] == 0:
                visited[j] = 1
                dfs(j,end,adj,array+[j],visited,depth+1)
                visited[j] = 0
            
def bfs(start,end,adj,visited):
    global mini
    queue = []
    queue.append(start)
    while queue:
        mini += 1
        for _ in range(len(queue)):
            curr = queue[0]
            queue.pop(0)
            for i in range(len(curr)):
                string = curr[:i]+"_"+curr[i+1:]
                for k in adj[string]:
                    if end == k:
                        return 
                    elif visited[k] == 0:
                        visited[k] = 1
                        queue.append(k)
                    
def adjdictbuilder(dictV):
    mapper = {}
    for word in dictV:
        for i in range(len(word)):
            string = word[:i]+"_"+word[i+1:]
            mapper[string] = mapper.get(string,[])+[word]
    return mapper

class Solution:
    def findLadders(self, start, end, dictV):
        global res,mini 
        if start == end:
            return [[start]]
        mini = 0
        res = []
        dictV = set(dictV)
        adjList = adjdictbuilder(dictV)
        visited = {}
        for i in dictV:
            visited[i] = 0
        bfs(start,end,adjList,visited)
        for i in dictV:
            visited[i] = 0
        dfs(start,end,adjList,[start],visited,0)
        return res