<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 {
public:
    map<pair<int,int>,int> mp; 
    int dp(int i, int j, string &s, string &t){
        // cout<<i<<" "<<j<<" "<<endl; 
        if(i<0 || j<0){
            if(i>=0){
                return i+1;
            }
            if(j>=0){
                return j+1;
            }
            return 0;
        }
        // if(i==j){
        //     if(s[i]==s[j]){
        //         return 0;
        //     }
        //     else{
        //         return 1;
        //     }
        // }
        if(mp.count({i,j})){
            return mp[{i,j}];
        }
        int ans = 1e9;
        if(s[i]==t[j]){
            ans=min(ans,dp(i-1,j-1,s,t));

        }
        else{
            // cout<<i<<" "<<j<<"@@@"<<endl; 
            ans=min(ans,1+dp(i-1,j,s,t));
            ans=min(ans,1+dp(i,j-1,s,t));
            // ans=min(ans,2+dp(i-1,j-1,s,t));
        }

        return mp[{i,j}]=ans;
    }
    int minDistance(string word1, string word2) {
        int n = word1.size();
        int m = word2.size();
        // vector<vector<int>> mp(n+1, vector<int> (m+1,-1));
        return dp(n-1,m-1, word1, word2);
    }
};
53486