Portfolio


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


Input: word1 = "leetcode", word2 = "etco"
Output: 4


var minDistance = function(word1, word2) {
    let lcs = 0;
    
    if(word1 === word2){
        return 0;
    }

    // word2.length is short than word1.length
    if(word1.length < word2.length){
        [word1, word2] = [word2, word1];
    }
    
    const word1Len = word1.length;
    const word2Len = word2.length;
    const dp = Array.from({length: word1Len + 1}, () => Array(word2Len + 1).fill(0));

    for(let i = 1; i <= word1Len; i++){
        for(let j = 1; j <= word2Len; j++){
            const char1 = word1[i - 1];
            const char2 = word2[j - 1];
            
            if(char1 === char2){
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else{
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    
    lcs = dp[word1Len][word2Len];
    
    return (word1Len - lcs) + (word2Len - lcs);
};


const minDistance = (word1, word2) => {
  const word1Length = word1.length;
  const word2Length = word2.length;

  const arr = Array.from({ length: word1Length + 1 }, () =>
    new Array(word2Length + 1).fill(0)
  );
// n x m
 // sea eat
 //   e a t 
 // 0 0 0 0
s// 0 0 0 0
e// 0 1 1 1
a// 0 1 2 2

  for (let i = 1; i <= word1Length; i += 1) {
    for (let j = 1; j <= word2Length; j += 1) {
      const now1 = word1[i - 1];
      const now2 = word2[j - 1];

      if (now1 === now2) {
        arr[i][j] = Math.max(
          arr[i - 1][j - 1] + 1,
          arr[i - 1][j], 
					arr[i][j - 1]
        );
      } else {
        arr[i][j] = Math.max(arr[i - 1][j], arr[i][j - 1]);
      }
      // console.log(now1, now2, arr);
    }
  }
  return word1Length + word2Length - 2 * arr[word1Length][word2Length];
};


var minDistance = function(word1, word2) {
    const lcs = Array.from(Array(word1.length + 1), () => Array(word2.length + 1).fill(0));
    const firstWordLength = word1.length;
    const secondWordLength = word2.length;

    for (let m = 1; m <= firstWordLength; m++) {
        for (let n = 1; n <= secondWordLength; n++) {
            const isSameCharacter = word1[m - 1] === word2[n - 1];
            const maxSubsequenceTillNow = Math.max(lcs[m][n - 1], lcs[m - 1][n]);
            lcs[m][n] = isSameCharacter ? 1 + lcs[m - 1][n - 1] : maxSubsequenceTillNow;
        }
    }
    
    return firstWordLength + secondWordLength - 2 * lcs[firstWordLength][secondWordLength];
};

Delete Operation for Two Strings

풀이