<p>Given two strings <code>word1</code> and <code>word2</code>, return <em>the minimum number of operations required to convert <code>word1</code> to <code>word2</code></em>.</p>

<p>You have the following three operations permitted on a word:</p>

<ul>
	<li>Insert a character</li>
	<li>Delete a character</li>
	<li>Replace a character</li>
</ul>

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

<pre>
<strong>Input:</strong> word1 = &quot;horse&quot;, word2 = &quot;ros&quot;
<strong>Output:</strong> 3
<strong>Explanation:</strong> 
horse -&gt; rorse (replace &#39;h&#39; with &#39;r&#39;)
rorse -&gt; rose (remove &#39;r&#39;)
rose -&gt; ros (remove &#39;e&#39;)
</pre>

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

<pre>
<strong>Input:</strong> word1 = &quot;intention&quot;, word2 = &quot;execution&quot;
<strong>Output:</strong> 5
<strong>Explanation:</strong> 
intention -&gt; inention (remove &#39;t&#39;)
inention -&gt; enention (replace &#39;i&#39; with &#39;e&#39;)
enention -&gt; exention (replace &#39;n&#39; with &#39;x&#39;)
exention -&gt; exection (replace &#39;n&#39; with &#39;c&#39;)
exection -&gt; execution (insert &#39;u&#39;)
</pre>

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

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

'''
return min number of ops to convert shorter -> longer
 - counting
 - also have to do it ?

ops (per character):
- insert
- delete
- replace
- skip

shorter -> longer (left to right) (1-based indexing)
i, j
matches, so skip is an option
- skip -> edit_distance(i + 1, j + 1)
i, j (h, r)
does not match, skip is not an option
- replace -> edit_distance(i + 1, j + 1)
- delete -> edit_distance(i + 1, j)
- insert r -> edit_distance(i, j + 1)
result = 1 + min(replace, delete, insert)

does order matter? no, pick one and stick with it <------------------------------
 - horse -> ros (right to left)
    - delete e
    - skip s
    - delete r
    - replace h with r
    - total count: 3
 - intention -> execution (right to left)
    - skip
    - skip
    - skip
    - skip
    - replace n with u
    - replace e with c
    - replace t with e
    - replace n with x
    - replace i with e

since order doesn't matter and theres no side effects...
the problem can be broken down into independent subproblems
the most optimal solution to each subproblem is the most optimal solution to the problem

base case:
i == len(shorter) and j == len(longer) return 0
recursive case:
r(i, j) = 
if shorter[i] == longer[j] -> r(i + 1, j + 1)
else: 1 + min(r(i + 1, j + 1), r(i, j + 1), r(i +1, j))

recurrence relation:
i: [0, len(shorter)]
j: [0, len(longer)]
rr = i * j = len(shorter) * len(longer) # runtime and unoptimized space
'''

class Solution:
    def minDistance(self, shorter: str, longer: str) -> int:
        if len(shorter) > len(longer):
            shorter, longer = longer, shorter
        dp = [[len(shorter) - i for i in range(len(shorter) + 1)] for _ in range(len(longer) + 1)]
        for j in range(len(longer)-1, -1, -1):
            dp[j][len(shorter)] = len(longer) - j
            for i in range(len(shorter)-1, -1, -1):
                if shorter[i] == longer[j]:
                    dp[j][i] = dp[j+1][i+1]
                    continue
                dp[j][i] = 1 + min(dp[j+1][i+1], dp[j][i+1], dp[j+1][i])
        return dp[0][0]
        
22137