1function minDistance(word1: string, word2: string): number {
2    const n = word1.length;
3    const m = word2.length;
4
5    const dp: number[][] = Array.from({ length: n + 1 }, () => Array(m + 1).fill(0))
6
7    for (let i = 0; i <= n; i++) {
8        dp[i][0] = i;
9    }
10
11    for (let j = 0; j <= m; j++) {
12        dp[0][j] = j;
13    }
14
15    for (let i = 1; i <= n; i++) {
16        for (let j = 1; j <= m; j++) {
17            if (word1[i - 1] === word2[j - 1]) {
18                dp[i][j] = dp[i - 1][j - 1];
19            } else {
20	                dp[i][j] = Math.min(
21                    dp[i - 1][j],
22                    dp[i][j - 1],
23                    dp[i - 1][j - 1]
24                ) + 1
25            }
26        }
27    }
28
29    return dp[n][m]
30}

1function minDistance(word1: string, word2: string): number {
2	const memo: Map<string, number> = new Map();
3	cosnt dfs(word1.length, word2.length, word1, word2, memo)
4}
5
6function dfs(i: number, j: number, word1: string, word2: string, memo: Map<string, number>) {
7	const key = `${i},${j}`;
8	if(memo.has(key)) return memo.get(key)!;
9	
10	if(i === 0) return j;
11	if(j === 0) return i;
12
13	if(word1[i - 1] === word2[j - 1]) {
14		const res = dfs(i - 1, j - 1, word1, word2, memo);
15		memo.set(key, res)
16		return res;
17	}
18
19	const delete = dfs (i - 1, j, word1, word2, memo);
20	const insert = dfs(i, j - 1, word1, word2, memo);
21	const replace = dfs(i - 1, j - 1, word1, word2, memo);
22	
23	const res = Math.min(delete, insert, replace) + 1;
24	memo.set(key, res);
25	
26	return res
27}