class Solution:
    def editDistance(self, word1: str, word2: str) -> int:
        #dp[i][j] will be the least distance from word1[:i] to word2[:j]
        dp = [[0 for _ in range(len(word2)+1)] for _ in range(len(word1)+1)]
        for i in range(len(word1)+1):
            dp[i][0] = i
            for j in range(1,len(word2)+1):
                if i == 0:
                    dp[0][j] = j
                elif word1[i-1] == word2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1
        return dp[-1][-1]  
 
obj = Solution()
str1 = "saturday"
str2 = "sunday"
print(obj.editDistance(str1, str2))

Y2xhc3MgU29sdXRpb246CiAgICBkZWYgZWRpdERpc3RhbmNlKHNlbGYsIHdvcmQxOiBzdHIsIHdvcmQyOiBzdHIpIC0+IGludDoKICAgICAgICAjZHBbaV1bal0gd2lsbCBiZSB0aGUgbGVhc3QgZGlzdGFuY2UgZnJvbSB3b3JkMVs6aV0gdG8gd29yZDJbOmpdCiAgICAgICAgZHAgPSBbWzAgZm9yIF8gaW4gcmFuZ2UobGVuKHdvcmQyKSsxKV0gZm9yIF8gaW4gcmFuZ2UobGVuKHdvcmQxKSsxKV0KICAgICAgICBmb3IgaSBpbiByYW5nZShsZW4od29yZDEpKzEpOgogICAgICAgICAgICBkcFtpXVswXSA9IGkKICAgICAgICAgICAgZm9yIGogaW4gcmFuZ2UoMSxsZW4od29yZDIpKzEpOgogICAgICAgICAgICAgICAgaWYgaSA9PSAwOgogICAgICAgICAgICAgICAgICAgIGRwWzBdW2pdID0gagogICAgICAgICAgICAgICAgZWxpZiB3b3JkMVtpLTFdID09IHdvcmQyW2otMV06CiAgICAgICAgICAgICAgICAgICAgZHBbaV1bal0gPSBkcFtpLTFdW2otMV0KICAgICAgICAgICAgICAgIGVsc2U6CiAgICAgICAgICAgICAgICAgICAgZHBbaV1bal0gPSBtaW4oZHBbaS0xXVtqLTFdLGRwW2ktMV1bal0sZHBbaV1bai0xXSkrMQogICAgICAgIHJldHVybiBkcFstMV1bLTFdICAKCm9iaiA9IFNvbHV0aW9uKCkKc3RyMSA9ICJzYXR1cmRheSIKc3RyMiA9ICJzdW5kYXkiCnByaW50KG9iai5lZGl0RGlzdGFuY2Uoc3RyMSwgc3RyMikp