<p>Given two strings <code>word1</code> and <code>word2</code>, return <em>the minimum number of <strong>steps</strong> required to make</em> <code>word1</code> <em>and</em> <code>word2</code> <em>the same</em>.</p>

<p>In one <strong>step</strong>, you can delete exactly one character in either string.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> word1 = &quot;sea&quot;, word2 = &quot;eat&quot;
<strong>Output:</strong> 2
<strong>Explanation:</strong> You need one step to make &quot;sea&quot; to &quot;ea&quot; and another step to make &quot;eat&quot; to &quot;ea&quot;.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> word1 = &quot;leetcode&quot;, word2 = &quot;etco&quot;
<strong>Output:</strong> 4
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= word1.length, word2.length &lt;= 500</code></li>
	<li><code>word1</code> and <code>word2</code> consist of only lowercase English letters.</li>
</ul>

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        # cnt1, cnt2 = [0] * 26, [0] * 26

        # for w in word1:
        #     cnt1[ord(w) - ord('a')] += 1
        # for w in word2:
        #     cnt2[ord(w) - ord('a')] += 1
        
        # cnt_diff = [0] * 26
        # for i in range(26):
        #     cnt_diff[i] = abs(cnt1[i] - cnt2[i])
        
        # steps = sum(cnt_diff)

        # return steps

        n1, n2 = len(word1), len(word2)

        dp = [[0] * (n2+1) for _ in range(n1+1)]
        for i in range(1, n1+1):
            dp[i][0] = i
        for j in range(1, n2+1):
            dp[0][j] = j

        for i in range(1, n1+1):
            for j in range(1, n2+1):
                if word1[i-1] == word2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = min(
                        dp[i-1][j] + 1,   # delete from word1
                        dp[i][j-1] + 1,   # delete from word2
                        dp[i-1][j-1] + 2,
                    )
        
        print(dp)
        
        return dp[-1][-1]


22656