C, Recursive DFS, 8mS
Scan from the start while backtracking and exploring insert, delete and replace options, of course only when characters mismatch. As you can see below, memoizat
Scan from the start while backtracking and exploring insert, delete and replace options, of course only when characters mismatch. As you can see below, memoization helps to short-circuit numerous paths.\nMore details at [link](https://msreekan.com/2016/08/13/edit-distance/)\n![alt text](https://tekrants.files.wordpress.com/2016/08/editdistance.jpg)\n\n```\nvoid ml(char* w1, int o1, int l1, char* w2, int o2, int l2,\n        unsigned char *dp)\n{\n    int offst = o1 * (l2 + 1) + o2, od = (o1 + 1) * (l2 + 1) + o2;\n    int oi = o1 * (l2 + 1) + o2 + 1, r = 0;\n\n    if (o1 == l1 || o2 == l2) // end of string, return remaining bytes\n        dp[offst] = (o1 == l1) ? l2 - o2 : l1 - o1;\n\n    /* If the minimum distance for strings at [o1..l1] & [o2..l2] is\n       not already calculated, then figure out the same */\n    else if (dp[offst] == MAX_CHAR)\n    {\n        if (w1[o1] != w2[o2]) // unequal characters\n        {\n            ml(w1, o1 + 1, l1, w2, o2, l2, dp); // delete\n            ml(w1, o1, l1, w2, o2 + 1, l2, dp); // insert\n            r++;\n        }\n\n        ml(w1, o1 + 1, l1, w2, o2 + 1, l2, dp); // replace/chars equal\n        dp[offst] = (r > 0) ? (MIN_INT(dp[od + 1] + r, dp[od] + r,\n                    dp[oi] + r)) : dp[od + 1]; // pick minimum\n    }\n}\n\nint minDistance(char *word1, char * word2)\n{\n    int l1 = strlen(word1), l2 = strlen(word2), md = 0;\n    unsigned char *dp = malloc((l1 + 1) * (l2 + 1) * sizeof(unsigned char));\n\n    /* Validate */\n    if (!dp) return 0;\n\n    /* Initialize buffer */\n    memset(dp, MAX_CHAR, (l1 + 1) * (l2 + 1));\n\n    /* Get the minimum distance */\n    ml(word1, 0, l1, word2, 0, l2, dp);\n    md = dp[0];\n    free(dp);\n    return md;\n}\n```\n\nEDIT : Just posted more details at the blog [link](https://msreekan.com/2016/08/13/edit-distance/)
['Recursion', 'C']