Leetcode583 Delete Operation for Two Strings解題報(bào)告

題意

Given two words word1 and word2, find the minimum number of steps required to make word1 and word2 the same, where in each step you can delete one character in either string.

Example 1:
Input: "sea", "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".
Note:
The length of given words won't exceed 500.
Characters in given words can only be lower-case letters.

簡單來說就是給你兩個(gè)字符串，做幾次操作可以使得兩個(gè)串相等（每次操作只能刪除一個(gè)字符）谁不。

思路

遞歸的解法

那么我們應(yīng)該可以想到這其實(shí)就是求兩個(gè)字符串的最長公共子串坐梯。因?yàn)橹灰覀冎懒诉@兩個(gè)字符串的最長公共子串，答案就是s1.length + s2.length - 2 * longest common string刹帕。
求最長公共子串的話可以進(jìn)行遞歸求解吵血。

function getLongestCommonString (s1, s2, m, n) {
    if (s[m] === s[n]) {
        return arguments.callee(s1, s2, m - 1, n - 1)
    } else {
        return Math.max(arguments.callee(s1, s2, m, n - 1), arguments.callee(s1, s2, m - 1, n))
    }
}

其實(shí)看代碼就很明白，如果兩個(gè)串最后一個(gè)字符對上了，那么它的結(jié)果就是s1[0:m-1]和s2[0:n-1]的最長公共子串?dāng)?shù)量加上1护锤。如果對不上胸私，那就是等于s1[0:m-1]和s2[0:n]的最長公共子串?dāng)?shù)量和s1[0:m]和s2[0:n-1]的最長公共子串?dāng)?shù)量兩者的最大值。進(jìn)行一次遞歸就可以得到結(jié)論侦另，最后用計(jì)算公式得到操作次數(shù)。

dp的解法

這道題也可以用dp來做尉共，算法上和遞歸解答思路是相近的褒傅。我們用二維數(shù)組來存狀態(tài)。dp[i][j]表示s1[0:i]和s2[0:j]的最長公共子串袄友，那么我們只需要在字符對上時(shí)殿托，dp[i][j] = dp[i - 1][j - 1] + 1，對不上時(shí)剧蚣，dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])就行了支竹，注意一下邊界值即可。

/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance = function(word1, word2) {
    if (word1.length === 0 || word2.length === 0) {
        return word1.length > word2.length ? word1.length:word2.length
    }
    var store = new Array()
    for (var i = 0; i < 501; i++) {
        store[i] = new Array()
    }
    for (var i = 0; i < word1.length; i++) {
        for (var k = 0; k < word2.length; k++) {
            if (word1[i] === word2[k]) {
                if (i === 0) {
                    store[0][k] = 1
                } else if (k === 0) {
                    store[i][0] = 1
                } else {
                    store[i][k] = store[i - 1][k - 1] + 1
                }
            } else {
                if (i === 0 && k === 0) {
                    store[0][0] = 0                    
                } else if (i === 0) {
                    store[0][k] = store[0][k - 1]
                } else if (k === 0) {
                    store[i][0] = store[i - 1][0]
                } else {
                    store[i][k] = Math.max(store[i][k - 1], store[i - 1][k])
                }
            }
        }
    }
    return word1.length + word2.length - 2 * store[word1.length - 1][word2.length - 1]
};

代碼效率不咋的券敌。唾戚。。