Find all paths - 9/19/2019 10:00 PM mock interview

FindAllPaths.py

def diff(w1, w2):
    delta = 0
    
    for i in range(len(w1)):
        x, y = w1[i], w2[i]
        if x != y:
            delta += 1

    return delta
        
 #   good->bood->beod->besd->best path -> contains 6 words -> paths -> how path starts from good, append goot
#good->goot->gost->gest->best  how path work on second path

all_paths = []
def dfs(src, trg, words, path):
    if src == trg:
        path.append(trg)
        all_paths.append(path)  # have five words 
    else:
        # go over each word in dctionary 1 million 
        # go over all possible neighbor 25 * 4 = 100 go over 
        #good - index =0, 1, 2, 3
        # = 0, g -> a - z except g, only 25 choices
        # = 1, 
        # = 2
        # = 3
        # preprocess dictionary - use trie
        neighbors = [w for w in words if diff(w, src) == 1 and w not in path]
        for neighbor in neighbors:   # two neighbors of "good", bood, goot
            path.append(neighbor)  # append - increase -> remove the path -> all paths -> design -> do you think that your design is ok? 
            
            dfs(neighbor, trg, words, path)
            # backtracking
            path.remove(path.Length - 1)  # remove last one
    

source = "good";
dest = "best";
words = ["beod", "besd","goot","gost","gest","best"]
        

path = []
dfs(source, dest, words, path)

for path in all_paths:
    print (path)




'''
source = "good";
dest = "best";

var words = new string[] {"24", "beod", "besd","goot","gost","gest","best"};

four characters, unique words -> upper bound O(26^4)= (100/4)^4 = 10^8 / (2^8)<1024= 1,000,000

two paths
good->bood->beod->besd->best
good->goot->gost->gest->best

Given a start and destination word
    , a list of words as a dictionary
    , find all paths from source to dest word
    , each intermediate word should be in dictionary. 
Each time one char is updated.
'''