Commented Intuitive python top-down dp


#1
class Solution:
    def minDistance(self, sA, sB):
        dp = {}											#initialize lookup dictionary
        def helper(A, B):
            if (not A) and (not B):						#both strings are empty, nothing to compare
                return 0
            elif dp.get((A, B)) == None:				#check if key for these two strings is absent in dict
                
                if A and B and A[0] == B[0]:			#if first character matches in both strings, recur for remaining part of strings
                    dp[(A, B)] = helper(A[1:], B[1:])
                else:
                    if not A:							#string A is empty and B is not empty, we need to add some characters to A to make it equal to B
                        dp[(A, B)] = len(B)
                    elif not B:
                        dp[(A, B)] = len(A)				#string B is empty and A is not empty, we need to delete some characters from A to make it equal to B				
                    
                    else:								#first characters don't match 
                        
                        dp[(A, B)] = 1+min(helper(A[1:], B[1:]),	#make A's first char same as that of B and recur for remaining part
                                            helper(A, B[1:]),		#insert B's first char at starting of A and recur for remaining part
                                            helper(A[1:], B))		#delete A's first char and recur for remaining part
            return dp[(A, B)]
            
        return helper(sA, sB)