<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:
    int minDistance(string word1, string word2) {
        string temp;
        if (word1.size() < word2.size()) {
            temp = word1;
            word1 = word2;
            word2 = temp;
        }
        if (word1.size() == 0)
            return word2.size();
        if (word2.size() == 0)
            return word1.size();
        if (word1[0] == word2[0])
            return minDistance(word1.substr(1), word2.substr(1));
        if (word1.back() == word2.back())
            return minDistance(word1.substr(0, word1.size()-1), word2.substr(0, word2.size()-1));
        if (word1.size() == 1) 
            if (word2.find(word1) != string::npos)
                return word2.size()-1;
            else
                return word2.size();
        if (word2.size() == 1)
            if (word1.find(word2) != string::npos)
                return word1.size()-1;
            else
                return word1.size();
        int max_j = 0;
        vector<vector<int>> marked_pair;
        cout << word1 << ' ' << word2 << endl;
        unordered_map<string, int> record;
        for (int i=0; i<word2.size()-max_j+1; i++) {
            int idx = 0;
            if (max_j == 0)
                idx = word1.find(word2[i]);
            else if (record.contains(word2.substr(i, max_j)))
                idx = word1.find(word2.substr(i, max_j), record[word2.substr(i, max_j)]+1);
            else
                idx = word1.find(word2.substr(i, max_j));
            cout << "idx " << idx << " i " << i << endl;
            while (idx != string::npos) {
                int j;
                for (j=max_j; i+j<word2.size() && idx+j<word1.size(); j++) {
                    if (word2[i+j] != word1[idx+j]) 
                        break;
                }
                cout << "j "  << j << " max_j " << max_j << endl;
                if (max_j <= j) {
                    int left_max = i < idx ? idx : i;
                    int right_max = (word1.size()-idx-j) < (word2.size()-i-j) ? (word2.size()-i-j) : (word1.size()-idx-j);
                    if (left_max + right_max <= word1.size()) {
                        if (max_j < j) {
                            max_j = j;
                            marked_pair.clear();
                            record.clear();
                        }
                        vector<int> temp{i, idx};
                        marked_pair.push_back(temp);
                        record[word2.substr(i, max_j)] = idx;
                    }
                }
                if (max_j == 0)
                    idx = word1.find(word2[i], idx+1);
                else
                    idx = word1.find(word2.substr(i, max_j), idx+1);
            }
        }
        if (max_j == 0) 
            return word1.size();
        vector<vector<int>> edit_method{marked_pair[0]};
        vector<vector<vector<int>>> edit_methods{edit_method};
        for (auto pa=marked_pair.begin()+1; pa!=marked_pair.end(); pa++) {
            bool new_begin = true;
            for (auto met = edit_methods.begin(); met != edit_methods.end(); met ++) {
                if (pa->at(1) > met->back()[1] && pa->at(0) > met->back()[0]) {
                    met->push_back(*pa);
                    new_begin = false;
                }
            }
            if (new_begin) {
                vector<vector<int>> new_method{*pa};
                edit_methods.push_back(new_method);
            }
        }
        int min_distance = word1.size();
        for (auto method=edit_methods.begin(); method!=edit_methods.end(); method ++) {
            int total_distance = 0;
            vector<vector<int>> pairs;
            vector<int> begin_pair{-max_j, -max_j};
            pairs.push_back(begin_pair);
            pairs.insert(pairs.end(), method->begin(), method->end());
            vector<int> end_pair{(int)word2.size(), (int)word1.size()};
            pairs.push_back(end_pair);
            for (int i=0; i<pairs.size()-1; i++) {
            cout << "in split" << endl;
            cout << word1.substr(pairs[i][1]+max_j, pairs[i+1][1]-pairs[i][1]-max_j) << endl;
            cout << word2.substr(pairs[i][0]+max_j, pairs[i+1][0]-pairs[i][0]-max_j) << endl;
            total_distance += minDistance(word1.substr(pairs[i][1]+max_j, pairs[i+1][1]-pairs[i][1]-max_j),
                word2.substr(pairs[i][0]+max_j, pairs[i+1][0]-pairs[i][0]-max_j));
            }
            if (min_distance == -1 || min_distance > total_distance)
                min_distance = total_distance;
        }
        // int total_distance = 0;
        // vector<vector<int>> pairs;
        // vector<int> begin_pair{-max_j, -max_j};
        // pairs.push_back(begin_pair);
        // pairs.insert(pairs.end(), marked_pair.begin()+max_begin_idx, marked_pair.begin()+max_begin_idx+max_increase);
        // vector<int> end_pair{(int)word2.size(), (int)word1.size()};
        // pairs.push_back(end_pair);
        // // cout << max_j << endl;
        // for (int i=0; i<pairs.size()-1; i++) {
        //     cout << "in split" << endl;
        //     cout << word1.substr(pairs[i][1]+max_j, pairs[i+1][1]-pairs[i][1]-max_j) << endl;
        //     cout << word2.substr(pairs[i][0]+max_j, pairs[i+1][0]-pairs[i][0]-max_j) << endl;
        //     total_distance += minDistance(word1.substr(pairs[i][1]+max_j, pairs[i+1][1]-pairs[i][1]-max_j),
        //         word2.substr(pairs[i][0]+max_j, pairs[i+1][0]-pairs[i][0]-max_j));
        // }
        return min_distance;
    }
};
16883