Skip to content

Instantly share code, notes, and snippets.

@ufo22940268

ufo22940268/712.js

Created May 31, 2021 01:42
Download ZIP

Revisions

  1. ufo22940268 created this gist May 31, 2021.
    81 changes: 81 additions & 0 deletions 712.js
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,81 @@
    //Given two strings s1, s2, find the lowest ASCII sum of deleted characters to m
    //ake two strings equal.
    //
    // 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 pos
    //sible 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.
    //
    //
    //
    // Note:
    // 0 < s1.length, s2.length <= 1000.
    // All elements of each string will have an ASCII value in [97, 122].
    // Related Topics 动态规划
    // 👍 218 👎 0


    //leetcode submit region begin(Prohibit modification and deletion)
    /**
    * @param {string} s1
    * @param {string} s2
    * @return {number}
    */
    var minimumDeleteSum = function (s1, s2) {
    const dp = new Array(s1.length + 1).fill(0)
    .map(_ => new Array(s2.length + 1).fill(0));

    function dfs(i, j) {
    if (i == 0 && j == 0) return 0;

    if (dp[i][j]) {
    return dp[i][j];
    }

    let s1c = s1.charCodeAt(i - 1);
    let s2c = s2.charCodeAt(j - 1);

    let ar = [];
    if (s1c == s2c) {
    ar.push(dfs(i - 1, j - 1));
    }

    if (i > 0) {
    ar.push(dfs(i - 1, j) + s1c);
    }

    if (j > 0) {
    ar.push(dfs(i, j - 1) + s2c);
    }

    let r = Math.min(...ar);
    dp[i][j] = r;
    return r;
    }

    return dfs(s1.length, s2.length);
    // return dp[s1.length][s2.length];
    };
    //leetcode submit region end(Prohibit modification and deletion)

    const r = minimumDeleteSum('sea', 'eat');
    console.log(`r: ` + JSON.stringify(r, null, 4) + '\n')