<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:
    unordered_map<string,int> um;
    int f(string& w1, string& w2, int i, int j, vector<vector<int>> &dp)
    {
        if(i==w1.size()) return w2.size()-j;
        if(j==w2.size()) return w1.size()-i;
        string key = to_string(i)+","+to_string(j);
        if(um.find(key)!=um.end()) return um[key];
        if(w1[i]==w2[j]) return f(w1, w2, i+1, j+1,dp);
        if(dp[i][j]!=-1) return dp[i][j];
        return um[key] = dp[i][j]= 1+min({f(w1,w2,i+1,j,dp), // delete
                    f(w1,w2,i+1,j+1,dp), // replace
                    f(w1,w2,i,j+1,dp)});//insertion
    }
    int minDistance(string w1, string w2) {
        vector<vector<int>> dp(w1.size(),vector<int>(w2.size(),-1));
        return f(w1,w2,0,0,dp);
    /*
    Approach: would need to do brute force
    if any of the word is empty return the length of other word because they would need to be removed
    1. if chars are same then find the mindistance from next characters onwards.
    2. if not then try deleting the current character i.e 1+f(for next character of word1)
    3. also try inserting the next character 1+f(for next char of word2)
    4. return min of them 
    */
    }
};
28013