<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>

class Solution {
public:

    /*
        01234
        horse
    0 r 12234 j-1+(same or not)
    1 o i1234 min((j-1,i-1),i-1)+same or not
    2 s ii223 
    */

    const int IMAX = int(1e5);
    string w1, w2;
    map<pair<int,int>,int> memo;
    int dp(int i1, int i2) {
        if(i1 >= w1.size() && i2 >= w2.size()) return 0;
        if(i1 >= w1.size() && i2 < w2.size()) return w2.size()-i2;
        if(i2 >= w2.size()) return w1.size()-i1;
        if(memo.find({i1,i2}) != memo.end()) return memo[{i1,i2}];
        // cout<<i1<<" "<<i2<<"\n";
        if(w1[i1] == w2[i2]) {
            return dp(i1+1, i2+1);
        }
        int del = IMAX, repl = IMAX, ins = IMAX;
        del = dp(i1+1,i2) + 1;
        ins = dp(i1,i2+1) +1;
        repl = dp(i1+1,i2+1)+1;

        int mini = min(del, min(ins, repl));
        // for(int i=0;i<=i1;i++) cout<<w1[i];
        // cout<<" ";
        // for(int i=0;i<=i2;i++) cout<<w2[i];
        // cout<<" "<<mini<<": "<<del<<" "<<ins<<" "<<repl<<"\n";
        return memo[{i1,i2}] = mini;
    }

    int minDistance(string word1, string word2) {
        w1 = word1, w2 = word2;
        return dp(0,0);
    }
};
20593