LeetCode: Delete Operation For Two Strings Solution

1/**
2 * @param {string} word1
3 * @param {string} word2
4 * @return {number}
5 */
6var minDistance = function (word1, word2) {
7  const getLcs = (word1, word2) => {
8    const getKey = (i, j) => `${i}-${j}`
9
10    const recursion = (word1, word2, i, j, memo = {}) => {
11      if (memo[getKey(i, j)] !== undefined) {
12        return memo[getKey(i, j)]
13      }
14
15      if (i === 0 || j === 0) {
16        return 0
17      }
18
19      if (word1[i - 1] === word2[j - 1]) {
20        return (memo[getKey(i, j)] =
21          1 + recursion(word1, word2, i - 1, j - 1, memo))
22      }
23
24      return (memo[getKey(i, j)] = Math.max(
25        recursion(word1, word2, i - 1, j, memo),
26        recursion(word1, word2, i, j - 1, memo)
27      ))
28    }
29
30    return recursion(word1, word2, word1.length, word2.length)
31  }
32
33  return word1.length + word2.length - 2 * getLcs(word1, word2)
34}