LeetCode 161. 相隔为 1 的编辑距离

LeetCode 161. 相隔为 1 的编辑距离

思路：

Dp O(n^2)

f[i][j]表示为如何对s的 1~i 修改可以匹配 t的1~j
三种情况：
删除 f[i - 1][j] + 1 删除a[i]
添加 f[i][j-1] + 1 添加 b[j]
修改 if(s[i] == t[j]) f[i - 1][j - 1] else f[i - 1][j - 1] + 1 修改s[i]

遍历枚举 O(n)

代码：
Dp

class Solution {
public:
    //如何对s的 1~i 修改可以匹配 t的1~j
    //删除 f[i - 1][j] + 1 删除a[i]
    //添加 f[i][j-1] + 1    添加 b[j]
    //修改 if(s[i] == t[j]) f[i - 1][j - 1] else f[i - 1][j - 1] + 1 修改s[i]
    vector<vector<int>> f;
    bool isOneEditDistance(string s, string t) {
        int n = s.size();
        int m = t.size();
        if(abs(n - m) > 1) return false;
        if(n==m)
        {
            int cnt=0;
            for(int i=0;i<n;i++)cnt+=(s[i]==t[i]);
            return cnt==n-1;
        }

        f = vector<vector<int>> (n + 1,vector<int> (m + 1));
        s = ' ' + s;
        t = ' ' + t;
        //Dp
        for(int i = 1;i <= n;i++) f[i][0] = i;
        for(int i = 1;i <= m;i++) f[0][i] = i;

        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= m;j++){
                f[i][j] = min(f[i-1][j],f[i][j-1]) + 1;
                if(s[i] == t[j]) f[i][j] = min(f[i][j] , f[i - 1][j - 1]);
                else f[i][j] = min(f[i][j],f[i - 1][j - 1] + 1);
            }
        }
        return f[n][m] == 1;
    }
};

枚举

class Solution {
public:
    bool isOneEditDistance(string s, string t) {
        //讨论几种情况 可以是O(n)的
        //Dp是O(n^2)的
        int n = s.size();
        int m = t.size();
        if(abs(n - m) > 1) return false;
        if(n == m){
            int cnt = 0;
            for(int i = 0;i < n;i++) if(s[i] != t[i]) cnt++;
            return cnt == 1;
        }
        //剩下的就是长度不同但是长度相差1
        return IsSameSubOne(s,t);
    }
    //s是长的
    bool IsSameSubOne(string &s,string &t){
        if(s.size() < t.size()) return IsSameSubOne(t,s);
        int cnt = 0;
        for(int i = 0,j = 0;i < s.size();){
            if(s[i] == t[j]) cnt++,i++,j++;
            else i++; 
        }
        return cnt == t.size();
    }
};