<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 getLongestCommonSubseq(self, index_1: int, index_2: int,
        n: int, m: int, word1: str, word2: str, cache: Dict) -> int:

        if index_1 == n or index_2 == m:
            return 0
        
        elif (index_1, index_2) in cache:
            return cache[(index_1, index_2)]
        
        elif word1[index_1] == word2[index_2]:
            cache[(index_1, index_2)] = 1 + self.getLongestCommonSubseq(index_1 + 1, index_2 + 1, n, m, word1, word2, cache)
            return cache[(index_1, index_2)]
        
        cache[(index_1, index_2)] =  max(
            self.getLongestCommonSubseq(index_1, index_2 + 1, n, m, word1, word2, cache),
            self.getLongestCommonSubseq(index_1 + 1, index_2, n, m, word1, word2, cache)
        )

        return cache[(index_1, index_2)]

    def minDistanceRec(self, word1: str, word2: str) -> int:
        n, m = len(word1), len(word2)
        cache = dict()

        return n + m - 2 * self.getLongestCommonSubseq(0, 0, n, m, word1, word2, cache)

    def minDistanceTab(self, word1: str, word2: str) -> int:
        n, m = len(word1), len(word2)

        dp = [
            [0] * (m + 1) for _ in range(n + 1)
        ]

        for index_1 in reversed(range(n + 1)):
            for index_2 in reversed(range(m + 1)):

                if index_1 == n or index_2 == m:
                    dp[index_1][index_2] = 0
                
                elif word1[index_1] == word2[index_2]:
                    dp[index_1][index_2] = 1 + dp[index_1 + 1][index_2 + 1]
                
                else:
                    dp[index_1][index_2] = max(
                        dp[index_1 + 1][index_2],
                        dp[index_1][index_2 + 1]
                    )         

        return n + m - 2 * dp[0][0]

    def minDistance(self, word1: str, word2: str) -> int:
        n, m = len(word1), len(word2)

        dp = [
            [0] * (m + 1) for _ in range(2)
        ]

        for index_1 in reversed(range(n)):
            for index_2 in reversed(range(m + 1)):
                
                if index_2 == m:
                    dp[0][index_2] = 0
                
                elif word1[index_1] == word2[index_2]:
                    dp[0][index_2] = 1 + dp[1][index_2 + 1]
                
                else:
                    dp[0][index_2] = max(
                        dp[1][index_2],
                        dp[0][index_2 + 1]
                    )

            for index_2 in range(m + 1):
                dp[1][index_2] = dp[0][index_2]

        return n + m - 2 * dp[0][0]
16741