原题链接在这里:
题目:
Given two strings s1, s2
, find the lowest ASCII sum of deleted characters to make two strings equal.
Example 1:
Input: s1 = "sea", s2 = "eat"Output: 231Explanation: 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: 403Explanation: 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.
Note:
0 < s1.length, s2.length <= 1000
.- All elements of each string will have an ASCII value in
[97, 122]
.
题解:
For two strings, dp[i][j] denotes s1 up to i and s2 up to j, minimum ASCII delete sum for two substrings.
There could be 2 cases:
case 1:
s1.charAt(i) == s2.charAt(j), then it doesn't need to delete last characters, dp[i][j] = dp[i-1][j-1].
case 2:
s1.charAt(i) != s2.charAt(j). then minimum delete could comes from 2 possibilities, take the minimum:
- delete s1.charAt(i). dp[i][j] = dp[i-1][j] + s1.charAt(i).
- delete s2.charAt(j). dp[i][j] = dp[i][j-1] + s2.charAt(j).
Time Complexity: O(m*n). m = s1.length(). n = s2.length().
Space: O(m*n).
AC Java:
1 class Solution { 2 public int minimumDeleteSum(String s1, String s2) { 3 int m = s1.length(); 4 int n = s2.length(); 5 int [][] dp = new int[m+1][n+1]; 6 7 for(int i = 1; i<=m; i++){ 8 dp[i][0] = dp[i-1][0]+s1.charAt(i-1); 9 }10 11 for(int j = 1; j<=n; j++){12 dp[0][j] = dp[0][j-1] + s2.charAt(j-1);13 }14 15 for(int i = 1; i<=m; i++){16 for(int j = 1; j<=n; j++){17 if(s1.charAt(i-1) == s2.charAt(j-1)){18 dp[i][j] = dp[i-1][j-1];19 }else{20 dp[i][j] = Math.min(dp[i-1][j]+s1.charAt(i-1), dp[i][j-1]+s2.charAt(j-1));21 }22 }23 }24 25 return dp[m][n];26 }27 }
类似, , .