Word ladder - find all paths - python - Sept. 17, 2019 10:00 PM mock interview

WordLadderFindAllPaths.py

def say_hello():
    print('Hello, World')

for i in range(5):
    say_hello()

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

// go through each char in source word - good
      index = 0, 1, 2, 3
  // go through 'a' to 'z' - replace the original
     brute force solution - let us exhaust all possible solutions
       index = 0
         'g' -> 'a'
         ..
         'g' ->'z'
       index = 1
          o -> a
          ..
          0 ->z
       index = 2
       index = 3
     
     

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

two paths
good->bood->beod->besd->best  <- do not know the length-N   O(100^N) good -> best -> goot start from dictionary
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. 

mark visit using hashset -> 
remove duplicated path 
DFS - depth first search 
path - maintain - shared space 
one variable path for all paths 

maintain - backtrack 
good -> bood ...
        remove bood from path,
        cood
        remove cood from path
 good ->bood->.....->best
                 besd<-
                 best<- 
                 b...
                 ...
path -> you -> add <- path -> increasing all the time, never decreasing 
maintain <- when to remove/ add
'''
def check_paths(visited, source, dest, dictionary, path, paths): # all paths - paths, one path - path
    #base_case:
    if(source == dest):
        paths.append(path)
        return
    str = "abcdefghijklmnopqrstuvwxyz"
    for i in range(len(source)):
        #good 
        char_arr = list(source)
        # source -> string to char array -> ToCharArray()
        for j in range(len(str)):
            if(char_arr[i] != str[j]):
                char_arr[i] = str[j]
            
            next_word = ''.join(char_arr)
            if next_word in dictionary:
                check_paths(next_word,dest,dictionary,
                            path.append(next_word), paths)   # DFS
                # you do not have logic to remove a word from path 
                # you have to design first 
                # all paths share one path varable -> insert/ remove 
                path.RemoveAT(lastPosition)  # remove next_word  -> path forever -> remove duplicate