Question 1:
Given two strings ， text1 ， and ， text2, return the length of the longest ， common subsequence ， of the two strings. If there is no {common subsequence, return} 0.
Subsequence of a string refers to such a new string: it is a new string composed of the original string after deleting some characters (or not deleting any characters) without changing the relative order of characters.
- For example, "ace" is a subsequence of "abcde", but "aec" is not a subsequence of "abcde".
The common subsequence of two strings is the subsequence shared by the two strings.
Example 1:
Input: text1 = "abcde", text2 = "ace" Output: 3 Explanation: the longest common subsequence is "ace", and its length is 3.
Example 2:
Input: text1 = "abc", text2 = "abc" Output: 3 Explanation: the longest common subsequence is "abc", and its length is 3.
Example 3:
Input: text1 = "abc", text2 = "def" Output: 0 Explanation: two strings have no common subsequence and return 0.
Tips:
- 1 <= text1.length, text2.length <= 1000
- text1 ， and ， text2 ， consist of lowercase English characters only.
1 class Solution { 2 public int longestCommonSubsequence(String text1, String text2) { 3 int l1=text1.length(),l2=text2.length(); 4 int[][] dp=new int[l1][l2]; 5 dp[0][0]=text1.charAt(0)==text2.charAt(0)?1:0; 6 for (int i=0;i<l1;i++) { 7 for (int j=0;j<l2;j++) { 8 if (text1.charAt(i)==text2.charAt(j)) { 9 if (i>0&&j>0) dp[i][j]=dp[i-1][j-1]+1; 10 else dp[i][j]=1; 11 }else { 12 if (i>0&&j>0) dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]); 13 else if (i>0) dp[i][j]=dp[i-1][j]; 14 else if (j>0) dp[i][j]=dp[i][j-1]; 15 } 16 } 17 } 18 return dp[l1-1][l2-1]; 19 } 20 }
Idea: dynamic programming. DP [i] [J] indicates the length of the longest common string between text1 0~i and text2 0~j. When the position strings of I and j are equal, the maximum value of DP [i] [J] should be dp[i-1][j-1]+1. When they are not equal, the longest common substring equivalent to 0~i-1 and 0~j or 0~i and 0~j-1 takes the maximum value. The final answer is dp[text1.len-1][text2.len-1].
We need to consider the case that the array is out of bounds. If I-1 and J-1 are out of bounds, it means that a string has only one letter and is equal. At this time, it must be 1 If the inequality exceeds the boundary, take the side that does not exceed the boundary. If both exceed the boundary, it means dp[0][0].
Question 2:
Given two words ， word1 ， and ， word2 ， returns the minimum number of steps required to make ， word1 ， and ， word2 ， the same.
One character in any string can be deleted in each step.
Example 1:
Input: word1 = "sea", word2 = "eat" Output: 2 Explanation: the first step is to change "sea" into "ea", and the second step is to change "eat" into "ea"
Example 2:
Input: word1 = "leetcode", word2 = "etco" Output: 4
Tips:
- 1 <= word1.length, word2.length <= 500
- word1 # and # word2 # contain only lowercase English letters
1 class Solution { 2 public int minDistance(String word1, String word2) { 3 int l1=word1.length(),l2=word2.length(); 4 int[][] dp=new int[l1][l2]; 5 dp[0][0]=word1.charAt(0)==word2.charAt(0)?1:0; 6 for (int i=0;i<l1;i++) { 7 for (int j=0;j<l2;j++) { 8 if (word1.charAt(i)==word2.charAt(j)) { 9 if (i>0&&j>0) dp[i][j]=dp[i-1][j-1]+1; 10 else dp[i][j]=1; 11 }else { 12 if (i>0&&j>0) dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]); 13 else if (i>0) dp[i][j]=dp[i-1][j]; 14 else if (j>0) dp[i][j]=dp[i][j-1]; 15 } 16 } 17 } 18 return l1+l2-dp[l1-1][l2-1]*2; 19 } 20 }
Idea: find the longest common substring, and then cut the total length. The common length is the minimum number of times.
Optimization: you can turn dp[i][j] into dp[i-1][j-1] to prevent handling cross-border situations.
1 class Solution { 2 public int minDistance(String word1, String word2) { 3 int m = word1.length(), n = word2.length(); 4 int[][] dp = new int[m + 1][n + 1]; 5 for (int i = 1; i <= m; i++) { 6 char c1 = word1.charAt(i - 1); 7 for (int j = 1; j <= n; j++) { 8 char c2 = word2.charAt(j - 1); 9 if (c1 == c2) { 10 dp[i][j] = dp[i - 1][j - 1] + 1; 11 } else { 12 dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); 13 } 14 } 15 } 16 return m+n-2*dp[m][n]; 17 } 18 }
Question 3:
Given the two strings S1 and S2, find the minimum sum of the ASCII values of the characters to be deleted to make the two strings equal.
Example 1:
Input: s1 = "sea", s2 = "eat" Output: 231 Explanation: delete "s" in "sea" and add the value of "s" (115) to the sum. Delete "t" from "eat" and add 116 to the sum. At the end, the two strings are equal, and 115 + 116 = 231 is the qualified minimum sum.
Example 2:
Input: s1 = "delete", s2 = "leet" Output: 403 Explanation: delete the "dee" string in "delete" and change it to "let", Add 100[d]+101[e]+101[e] to the sum. Delete "e" in "leet" and add 101[e] to the sum. At the end, both strings are equal to "let", and the result is 100 + 101 + 101 + 101 = 403. If we convert two strings to "lee" or "eet" instead, we will get the result of 433 or 417, which is larger than the answer.
be careful:
- 0 < s1.length, s2.length <= 1000.
- The ASCII values of characters in all strings are between [97, 122].
1 class Solution { 2 public int minimumDeleteSum(String s1, String s2) { 3 int[][] dp = new int[s1.length() + 1][s2.length() + 1]; 4 //Dynamic programming 5 //dp[i][j]express s1,i~len1-1 s2 j~len2-1 Minimum value of 6 //dp[i][len1] For another string ASCII accumulation 7 //dp[i][len2] Similarly 8 for (int i = s1.length() - 1; i >= 0; i--) { 9 dp[i][s2.length()] = dp[i+1][s2.length()] + s1.codePointAt(i); 10 } 11 for (int j = s2.length() - 1; j >= 0; j--) { 12 dp[s1.length()][j] = dp[s1.length()][j+1] + s2.codePointAt(j); 13 } 14 // Judgment and LCS When the method is similar and equal, it does not need to be deleted 15 // If not, delete the smaller one 16 for (int i = s1.length() - 1; i >= 0; i--) { 17 for (int j = s2.length() - 1; j >= 0; j--) { 18 if (s1.charAt(i) == s2.charAt(j)) { 19 dp[i][j] = dp[i+1][j+1]; 20 } else { 21 dp[i][j] = Math.min(dp[i+1][j] + s1.codePointAt(i), 22 dp[i][j+1] + s2.codePointAt(j)); 23 } 24 } 25 } 26 return dp[0][0]; 27 } 28 }
Idea: the first reaction is to find the common substring, but you need to find the specific substring. In fact, it can be abstracted into dynamic programming, dp[i][j] is the value of deleting letters. In addition, the direction of dp[i][j] is also different. See notes for details.