LeetCode开心刷题三十一天——72. Edit Distance

叁歲伎倆 2021-10-26 15:12 219阅读 0赞

72. Edit Distance

Hard

232635FavoriteShare

Given two words *word1* and *word2*, find the minimum number of operations required to convert *word1* to *word2*.

You have the following 3 operations permitted on a word:

1.  Insert a character
2.  Delete a character
3.  Replace a character

Example 1:

Input: word1 = "horse", word2 = "ros"
    Output: 3
    Explanation: 
    horse -> rorse (replace 'h' with 'r')
    rorse -> rose (remove 'r')
    rose -> ros (remove 'e')

Example 2:

Input: word1 = "intention", word2 = "execution"
    Output: 5
    Explanation: 
    intention -> inention (remove 't')
    inention -> enention (replace 'i' with 'e')
    enention -> exention (replace 'n' with 'x')
    exention -> exection (replace 'n' with 'c')
    exection -> execution (insert 'u')
    This question itself has a clear mind.
    First,divide into two main situation d1[i]==d2[j],
    if equal means don't need add distance,if not add 1
    except for all of this,each time you see it you need compare dp[i][j-1],dp[i-1][j],dp[i-1][j-1]
    select a minimum one.and don't forget to add extra distance.It's important to consider the whole
    picture.
    ATTENTION:
    Judge NULL situation can largely decrease the running time and bigger a bit space(NIPTTnot important)

#include<stdio.h>
    #include<iostream>
    #include<string>
    #include<vector>
    #include<set>
    #include<map>
    #include<algorithm>
    using namespace std;
    class Solution {
    public:
        int minDistance(string word1, string word2) {
            if(word1.empty()||word2.empty())
            {
          int tmp=word1.length()-word2.length();
                return abs(tmp);}
            //==situation
            int m=word1.length(),n=word2.length();int tmp=0;
            vector<vector<int>> dp= vector<vector<int>>(m + 1, vector<int>(n + 1, 0));
            for(int i=0;i<m+1;i++)
                dp[i][0]=i;
            for(int j=0;j<n+1;j++)
                dp[0][j]=j;
            for(int i=1;i<m+1;i++)
            {
                for(int j=1;j<n+1;j++)
                {
                    int c=(word1[i-1]==word2[j-1])?0:1;
                    dp[i][j]=min(min(dp[i-1][j],dp[i][j-1])+1,dp[i-1][j-1]+c);
                }
            }
            return dp[m][n];
        }
    };
    int main()
    {
        Solution s;
        //string word1="intention";string word2 = "execution";
        string word1 = "horse", word2 = "ros";
        //string s1=" ";
        int res=s.minDistance(word1,word2);
        cout<<res<<endl;
        return 0;
    }

转载于:https://www.cnblogs.com/Marigolci/p/11333138.html