题目描述:给定两个字符串s1, s2
,找到使两个字符串相等所需删除字符的ASCII值的最小和。
代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
| public class Node { private int seqLen; private int sumAsc; private String longestSeq;
public int getSeqLen() { return seqLen; }
public void setSeqLen(int seqLen) { this.seqLen = seqLen; }
public String getLongestSeq() { return longestSeq; }
public void setLongestSeq(String longestSeq) { this.longestSeq = longestSeq; }
public int getSumAsc() { return sumAsc; }
public void setSumAsc(int sumAsc) { this.sumAsc = sumAsc; }
public Node(int seqLen, int sumAsc, String longestSeq) { this.seqLen = seqLen; this.sumAsc = sumAsc; this.longestSeq = longestSeq; } }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
| class Solution { public int minimumDeleteSum(String s1, String s2) { Node maxNode = longestCommonSubsequence(s1.toCharArray(), s2.toCharArray()); int sumS1 = 0; for (int i = 0; i < s1.length(); i++) { sumS1 += s1.charAt(i); }
int sumS2 = 0; for (int i = 0; i < s2.length(); i++) { sumS2 += s2.charAt(i); }
int sumM = 0; for (int i = 0; i < maxNode.getLongestSeq().length(); i++) { sumM += maxNode.getLongestSeq().charAt(i); } return sumS1 + sumS2 - sumM * 2; }
private Node longestCommonSubsequence(char[] nums1, char nums2[]) { Node[][] dp = new Node[nums1.length + 1][nums2.length + 1]; for (int i = 0; i <= nums1.length; i++) { for (int j = 0; j <= nums2.length; j++) { dp[i][j] = new Node(0, 0, ""); } }
for (int i = 1; i <= nums1.length; i++) { for (int j = 1; j <= nums2.length; j++) { if (nums1[i - 1] == nums2[j - 1]) { dp[i][j].setSeqLen(dp[i - 1][j - 1].getSeqLen() + 1); dp[i][j].setLongestSeq(dp[i - 1][j - 1].getLongestSeq() + nums1[i - 1]); dp[i][j].setSumAsc(dp[i - 1][j - 1].getSumAsc() + nums1[i - 1]); } else { Node rNode = dp[i - 1][j]; Node cNode = dp[i][j - 1]; Node maxNode = null; if (rNode.getSeqLen() == cNode.getSeqLen()) { maxNode = rNode.getSumAsc() > cNode.getSumAsc() ? rNode : cNode; } else if (rNode.getSeqLen() < cNode.getSeqLen()) { maxNode = cNode; } else { maxNode = rNode; } dp[i][j] = maxNode; } } } return dp[nums1.length][nums2.length]; } }
|