Re: [閒聊] 每日LeetCode

https://leetcode.com/problems/minimum-ascii-delete-sum-for-two-strings/description/ 712. Minimum ASCII Delete Sum for Two Strings 給你兩個字串 s1 和 s2，求出被刪除的字元之最小ASCII和，可以使 s1 和 s2 兩字串相 等。 Example 1: Input: s1 = "sea", s2 = "eat" Output: 231 Explanation: Deleting "s" from "sea" adds the ASCII value of "s" (115) to the sum. Deleting "t" from "eat" adds 116 to the sum. At the end, both strings are equal, and 115 + 116 = 231 is the minimum sum possible to achieve this. Example 2: Input: s1 = "delete", s2 = "leet" Output: 403 Explanation: Deleting "dee" from "delete" to turn the string into "let", adds 100[d] + 101[e] + 101[e] to the sum. Deleting "e" from "leet" adds 101[e] to the sum. At the end, both strings are equal to "let", and the answer is 100+101+101+101 = 403. If instead we turned both strings into "lee" or "eet", we would get answers of 433 or 417, which are higher. 思路： 1.這題基本上就編輯距離的變種，作法是求 LCS 的 DP 作法，我們先稱他為MDS。 2.定義 dp[i][j] 為 s1 長度為 i 且 s2 長度為 j 的最小刪除和，先初始化第一行第 一列，對於長度為 0 的字串來說，MDS 一定是不為 0 的那個字串的所有字元和，因 為只有刪掉全部字元才會等於空字串，所以就按照長度累加ASCII值就好。 3.初始化完 DP 的第一行和第一列後，我們可以分成兩種 CASE： s1[i] = s2[j]：表示當前兩個字串的字元相同不需刪除，所以他的長度為上一個最小 s1[i] != s2[j]: dp[i][j]可能是長度為 dp[i-1][j] 或 dp[i][j-1] 的 MDS 刪除其 中一個字元獲得，取較小的。 4.dp更新完全部長度就完事 Java Code： -------------------------------------------- class Solution { public int minimumDeleteSum(String s1, String s2) { int n1 = s1.length(); int n2 = s2.length(); int[][] dp = new int[n1 + 1][n2 + 1]; for (int i = 1; i <= n1; i++) { dp[i][0] = dp[i - 1][0] + s1.charAt(i - 1); } for (int j = 1; j <= n2; j++) { dp[0][j] = dp[0][j - 1] + s2.charAt(j - 1); } for (int i = 1; i <= n1; i++) { int char1 = s1.charAt(i - 1); for (int j = 1; j <= n2; j++) { int char2 = s2.charAt(j - 1); if (char1 == char2) { dp[i][j] = dp[i - 1][j - 1]; } else { dp[i][j] = Math.min(dp[i - 1][j] + char1, dp[i][j - 1] + char2); } } } return dp[n1][n2]; } } -------------------------------------------- 咪 -- https://i.imgur.com/3e5CZfj.jpg --
※ 批踢踢實業坊(ptt.cc), 來自: 122.100.75.86 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1690818661.A.033.html