1function makeMatrix(row: number, col: number) { 2 return Array(row) 3 .fill(0) 4 .map(_ => Array(col).fill(Infinity)); 5} 6 7export default function minDistance(word1?: string, word2?: string): number { 8 if (!word1 || !word2) { 9 return word1?.length || word2?.length || 0; 10 } 11 12 const dp = makeMatrix(word1.length + 1, word2.length + 1); 13 14 for (let i = 0; i <= word1.length; ++i) { 15 for (let j = 0; j <= word2.length; ++j) { 16 if (i === 0 || j === 0) { 17 dp[i][j] = i || j; 18 continue; 19 } 20 const currentStr1 = word1[i - 1]; 21 const currentStr2 = word2[j - 1]; 22 if (currentStr1 === currentStr2) { 23 dp[i][j] = Math.min( 24 dp[i - 1][j - 1], 25 dp[i - 1][j] + 1, 26 dp[i][j - 1] + 1, 27 ); 28 } else { 29 dp[i][j] = Math.min( 30 dp[i - 1][j - 1] + 1, 31 dp[i - 1][j] + 1, 32 dp[i][j - 1] + 1, 33 ); 34 } 35 } 36 } 37 38 return dp[word1.length][word2.length]; 39} 40