leetcode 面试题 01.05. 一次编辑 动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    int min(int a, int b, int c) {
        int temp = a > b ? b : a;
        int result = c > temp ? temp : c;
        return result;
    }
    bool oneEditAway(string first, string second) {
        int m=first.length();
        int n=second.length();
        int dp[n+1];
        for(int i=0;i<=n;++i){
            dp[i]=i;  //刚开始dp[i]是从啥都没有变成word2前i个字符所需的步数
        }
        for(int j=1;j<=m;++j){    //分别遍历从有i个字符的word1变到word2的前i个字符所需步数dp[i]
            int tmp=dp[0];
            dp[0]=j;
            for(int i=1;i<=n;++i){
                int pre=tmp;
                tmp=dp[i];
                if(first[j-1]==second[i-1]){
                    dp[i]=pre;
                }else{
                    dp[i]=min(dp[i-1],pre,dp[i])+1;
                }
            }
        }
        return dp[n]<2;
    }
};