[Leetcode]583.Delete Operation for Two Strings

583.Delete Operation for Two Strings

題目連結
難易度：Medium

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:

Input: "sea", "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".

大意是，求最小的刪除次數讓兩字串相等，也就是找出最長公共子字串LCS(Longest Common Subsequence)的長度，這樣兩字串所需刪除數最少，而刪除的步數即等於兩字串長度相加並扣除兩倍的LCS長度。

思路

將word1、word2字串逐步拆解為兩部份sub1、e1，sub2、e2(e1、e2代表最後一字元)
使用DP，用一二維陣列lcslen來存lcs長度，此時會分為三種可能：

• 第一種為當e1 == e2 (表示兩字串某部份最後一字元相等時)，這時的lcslen就等同於lcslen[sub1][sub2]+1，+1表示相同的值所以長度+1。
• 第二種情況為e1 !== e2，此時lcslen又可分為兩種，lcslen[sub1][word2]、lcslen[word1][sub2]，找出兩者最大即可

解題

var minDistance = function(word1, word2) {
    var len1 = word1.length;
    var len2 = word2.length;
    var lcslen = [];
    function lcs(){
        for(var i=0; i<=word1.length;i++ ){
            for(var j=0; j<=word2.length;j++){
                //若兩字串為空集合，lcslen為0
                if(i==0 || j==0){
                    lcslen[i][j] = 0;
                //e1 == e2
                }else if(word1[i-1]==word2[j-1]){
                    lcslen[i][j] = lcslen[i-1][j-1]+1;
                }
                //e1 !== e2
                else{
                    lcslen[i][j] = Math.max(lcslen[i][j-1],lcslen[i-1][j]);
                }
            }
        }
        return lcslen[len1][len2];
    }
    return len1+len2 -2* lcs();
};