.dfs plus bfs solution with comments


#1

from collections import deque
import string
class Solution:

def findLadders(self, start, end, dictV):
    def dfs(end,mxd,li,res,d,d1,arr):
        #depth becomes max depth append if last word in li is end
        if d==mxd:
            if len(li)>0 and li[-1]==end:
                res.append(li[:])
            return
        temp=li[-1]
        for i in range(len(temp)):
            for x in arr:
                temp1=temp[:i]+x+temp[i+1:]
                if temp1 in d1:
                    li.append(temp1)
                    d1.pop(temp1)
                    dfs(end,mxd,li,res,d+1,d1,arr)
                    #backtrack for other results
                    li.pop()
                    d1[temp1]=1
    #calculate min depth for transformation
    def depth(start,end,d1):
        #all char from a to z 
        arr=list(string.ascii_lowercase)
        q=deque()
        #push start node to deque
        q.append([start,1])
        while(len(q)>0):
            temp,d=q.popleft()
            if temp==end:
                return d
            for i in range(len(temp)):
                for x in arr:
                    #replace character if after replacement word is in dict.
                    temp1=temp[:i]+x+temp[i+1:]
                    if temp1 in d1:
                        q.append([temp1,d+1])
                        d1.pop(temp1)
                    if temp1==end:
                        q.append([temp1,d+1])
        return -1
    #program start
    #store words in dictionary
    d1={}
    for x in dictV:
        d1[x]=1
    #find min depth using bfs
    d=depth(start,end,d1)
    if d==-1:
        return []
    #store words in dictionary
    d1={}
    for x in dictV:
        d1[x]=1
    #for storing final result
    res=[]
    #for storing temporary result
    li=[start]
    #from a to z in lowercase
    arr=list(string.ascii_lowercase)
    #peform dfs for depth d-1
    dfs(end,d-1,li,res,0,d1,arr)
    return res