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

    int minDistanceHelper(const string& word1, const string& word2, int idx1, int idx2, unordered_map<string, int>& memo) {
        string key = to_string(idx1) + "," + to_string(idx2);
        if (memo.find(key) != memo.end()) {
            return memo.at(key);
        }

        int solution = 0;
        if (idx1 < word1.size() && idx2 < word2.size()) {
            if (word1.at(idx1) == word2.at(idx2)) {
                solution = minDistanceHelper(word1, word2, idx1 + 1, idx2 + 1, memo);
            } else {
                int replace = minDistanceHelper(word1, word2, idx1 + 1, idx2 + 1, memo) + 1;
                int remove = minDistanceHelper(word1, word2, idx1 + 1, idx2, memo) + 1;
                int insert = minDistanceHelper(word1, word2, idx1, idx2 + 1, memo) + 1;

                solution = min(replace, min(remove, insert));
            }
        } else if (idx1 < word1.size() && idx2 >= word2.size()) {
            solution = word1.size() - idx1;
        } else if (idx2 < word2.size() && idx1 >= word1.size()) {
            solution = word2.size() - idx2;
        }
        
        memo.insert({key, solution});

        return solution;
    }

public:
    int minDistance(string word1, string word2) {
        // replace, increment idx1 and idx2 -> + 1
        // remove, increment idx1 -> + 1
        // insert, increment idx2 -> + 1
        // skip (already same) -> + 0
        unordered_map<string, int> memo;
        //pick min from these and return it
        return minDistanceHelper(word1, word2, 0, 0, memo);
    }
};
28013