31:T5fd,function minDistance(word1, word2) { // Done, the words match. if (word1 === word2) { return 0; } // The words will not match until both words are empty. if (word1.length === 0 || word2.length === 0) { return Math.max(word1.length, word2.length); } // Ensure word1 is shorter than word2. // Swap arguments if necessary. if (word1.length > word2.length) { return minDistance(word2, word1); } // Preprocess. let word1Dict = {}, word2Dict = {}; for (let k = 0; k < word2.length; k++) { if (k < word1.length) { word1Dict[word1.charAt(k)] = true; } word2Dict[word2.charAt(k)] = true; } let deleted = 0; // Remove characters from word1 that are not contained in word2. for (let i = 0; i < word1.length; i++) { if (!word2Dict[word1.charAt(i)]) { word1 = word1.substring(0, i) + word1.substring(i + 1); deleted++; } } // Remove characters from word2 that are not contained in word1. for (let j = 0; j < word2.length; j++) { if (!word1Dict[word2.charAt(j)]) { word2 = word2.substring(0, j,) + word2.substring(j + 1); deleted++; } } if (deleted > 0) { return deleted + minDistance(word1, word2); } let minDeletions = Infinity; for (let i = 0; i < word2.length; i++) { let deletions = minDistance(word1, word2.substring(0, i) + word2.substring(i + 1)); if (deletions < minDeletions) { minDeletions = deletions; } } return 1 + minDeletions; }32:[] 2f:{"title":"Dynamic Programming Problems","cells":[{"id":0,"value":"md`# Dynamic Programming Problems`","pinned":false,"hidden":false,"mode":"ojs"},{"id":2,"value":"md`## 1. Longest Common Subsequence`","pinned":false,"hidden":false,"mode":"ojs"},{"id":5,"value":"md`Given two words word1 and word2, find the minimum number of steps required to make word1 and word2 the same, where in each step you can delete one character in either string.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":8,"value":"md`### Solution`","pinned":false,"hidden":false,"mode":"ojs"},{"id":9,"value":"md`A dynamic programming solution without memoization runs the risk of being too slow. The following example is correct but will exceed time limits for even modest input strings. It's a decent first start, howerver.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":11,"value":"$31","pinned":true,"hidden":false,"mode":"ojs"},{"id":17,"value":"md`Technically, without memoization, it can be said that the above solution does not really conform to the notion of *dynamic programming*.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":19,"value":"md`## Another Solution`","pinned":false,"hidden":false,"mode":"ojs"},{"id":20,"value":"function lcs(x, y) {\n // dp[row][col]\n let dp = (new Array(x.length + 1)).fill(0); \n \n // Create the columns.\n dp = dp.map((d, i) => (new Array(y.length + 1)).fill(0));\n \n // indices consider the zeroth row and column to be the empty\n // strings that include no common sequence from x and y, respectively.\n for (let r = 1; r < x.length + 1; r++) {\n for (let c = 1; c < y.length + 1; c++) {\n // Indices into the strings are offset from those\n // into the rows and columns by one \"less\" than the row/col.\n if (x.charAt(r - 1) === y.charAt(c - 1)) {\n dp[r][c] = 1 + dp[r - 1][c - 1];\n } else {\n dp[r][c] = Math.max(\n dp[r - 1][c],\n dp[r][c - 1]);\n }\n } \n }\n \n return dp[x.length][y.length];\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":24,"value":"lcs('foodies', 'dudes')","pinned":true,"hidden":false,"mode":"ojs"},{"id":117,"value":"lcs('pez', 'dispenser')","pinned":true,"hidden":false,"mode":"ojs"},{"id":123,"value":"lcs('perfect', 'perfect')","pinned":true,"hidden":false,"mode":"ojs"},{"id":125,"value":"lcs('substring', 'stringer')","pinned":true,"hidden":false,"mode":"ojs"},{"id":121,"value":"md`The next thing we might consider doing is writing a trace-back function that can make use of the dynamic programming table of longest common substring *lengths* in order to reconstruct the *path* taken through the table and therefore determine the actual LCS. This has the benefit of avoiding storing the partial solutions in the dynamic programming table, at the expense of performing some work to reconstruct the path.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":130,"value":"md`## 2. Decode Ways`","pinned":false,"hidden":false,"mode":"ojs"},{"id":131,"value":"md`[From LeetCode](https://leetcode.com/problems/decode-ways/)\n\nA message containing letters from A-Z is being encoded to numbers using the following mapping:\n\n\\`\\`\\`\n'A' -> 1\n'B' -> 2\n...\n'Z' -> 26\n\\`\\`\\`\n\nGiven a non-empty string containing only digits, determine the total number of ways to decode it.\n\nExample 1:\n\nInput: \"12\"\nOutput: 2\nExplanation: It could be decoded as \"AB\" (1 2) or \"L\" (12).\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":133,"value":"md`A first approach could make use of a top-down recursive function which keeps as an ugly tag-along argument the array of solutions if the solutions are needed. But if we only care about the *number* of possible decodings, we can omit this argument.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":145,"value":"/**\n * @param {string} s\n * @return {number}\n */\nfunction numDecodings(s, notepad) {\n \n if (s.length === 0 && notepad == null) {\n return 0;\n }\n \n if (notepad == null) {\n return numDecodings(s, { count: 0 });\n }\n \n if (s.length === 0) {\n notepad.count = notepad.count + 1;\n } else { // s.length greater than or equal to 1\n let a = parseInt(s.charAt(0), 10);\n \n if (a > 0) {\n numDecodings(s.substring(1), notepad);\n \n if (s.length > 1) { // Possible to create a two-digit decoding.\n let b = parseInt(s.substring(0, 2), 10);\n\n if (b > 0 && b < 27) {\n numDecodings(s.substring(2), notepad);\n }\n }\n }\n }\n \n return notepad.count;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":155,"value":"md`The above solution appears to be correct, but it exceeds time limits on large inputs given by LeetCode. Memoization may be a possible work-around. But it is difficult to see how we could memoize this function. A better approach involves finding a supbroblem (overlap) relation and building a dynamic programming table.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":158,"value":"md`The relation we are looking to exploit is the following:\n\n\\`\\`\\`\ndp[n] = dp[n - 1] + dp[n - 2]\n\\`\\`\\`\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":160,"value":"function decode2(s) {\n if (s.length === 0 || s.charAt(0) == '0') {\n return 0;\n }\n \n if (s.length === 1) {\n return 1;\n }\n \n let dp = (new Array(s.length)).fill(0);\n dp[0] = 1;\n \n let b = parseInt(s.substring(0, 2), 10);\n \n if (b > 26) {\n if (s.charAt(1) === '0') {\n dp[1] = 0; // Invalid encoding.\n } else {\n dp[1] = 1;\n }\n } else {\n if (s.charAt(1) == '0') {\n dp[1] = 1;\n } else {\n dp[1] = 2;\n }\n }\n \n for (let i = 2; i < s.length; i++) {\n if (parseInt(s.charAt(i)) > 0) {\n dp[i] += dp[i - 1];\n }\n \n let b = parseInt(s.substring(i - 1, i + 1), 10);\n \n if (b < 27 && b >= 10) {\n dp[i] += dp[i - 2];\n }\n }\n \n return dp[s.length - 1];\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":169,"value":"decode2(\"2220222\")","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W32","stdlib":"1","titling":"auto"}