古生物血缘远近判定

2021-02-02

DNA 是由 ACGT 四种核苷酸组成，例如 AAAGTCTGAC，假定自然环境下 DNA 发生异变的情况有：

基因缺失一个核苷酸
基因新增一个核苷酸
基因替换一个核苷酸
且发生概率相同。
古生物学家 Sam 得到了若干条相似 DNA 序列，Sam 认为一个 DNA 序列向另外一个 DNA 序列转变所需的最小异变情况数可以代表其物种血缘相近程度，异变情况数越少，血缘越相近，请帮助 Sam 实现获取两条 DNA 序列的最小异变情况数的算法。

输入描述:

每个样例只有一行，两个 DNA 序列字符串以英文逗号“,”分割
输出描述:
输出转变所需的最少情况数，类型是数字

测试用例:
输入
ACT,AGCT
输出
1

数据范围：

每个 DNA 序列不超过 100 个字符

作者：字节校园
链接：https://leetcode-cn.com/leetbook/read/bytedance-c01/eug83v/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

动态规划

自顶向下的动态规划的思路是：选择最后一个字符，

如果两个字符串的第$i$,$j$个字符相同，继续判断第两个字符串的$i-1$，$j-1$的字符,即$dp[i][j]=dp[i-1][j-1]$
如果两个字符串的第$i$,$j$个字符相同，则继续判断第$i-1$,$j$个字符或者第$i$,$j-1$个字符

$\mathrm{d}[\mathrm{i}, \mathrm{j}] \rightarrow\left{\begin{array}{ll}
0 & \mathrm{i}=0, \mathrm{j}=0 \
\mathrm{j} & \mathrm{i}=0, \mathrm{j}>0 \
\mathrm{i} & \mathrm{j}>0, \mathrm{i}=0 \
\mathrm{d}[\mathrm{i}-1, \mathrm{j}-1] & \mathrm{S}_1(\mathrm{i})=\mathrm{S}_2(\mathrm{j}) \
\min (\mathrm{d}[\mathrm{i}, \mathrm{j}-1]+1, \mathrm{~~d}[\mathrm{i}-1, \mathrm{j}]+1, \mathrm{~~d}[\mathrm{i}-1, \mathrm{j}-1]+1) & \mathrm{S}_1(\mathrm{i}) \neq \mathrm{S}_2(\mathrm{j})
\end{array}\right.$

分析

定义：$S_1$、$S_2$表示两个字符串，$S_1(i)$表示$S_1$的第一个字符，$d[i, j]$表示$S_1$的第$i$个前缀到$S_2$的第$j$个前缀（例如:$S_1 = ”abc”,S_2 = ”def”$,求解$S_1$到$S_2$的编辑距离为$d[3, 3]$）。

若$S_1 = ”abc”, S_2 = ”dec”$，此时它们的编辑距离为$d[3, 3] = 2$，观察两个字符串的最后一个字符是相同的，也就是说$S_1(3) = S_2(3)$不需要做任何变换，故$S_1 = ”abc”, S_2 = ”dec”$ <=>$S_1’ = ”ab”, S_2’ = ”de”$，即当$S_1[i] = S[j]$时，$d[i, j] = d[i-1,j -1]$。得到公式：$d[i, j] = d[i - 1, j - 1] (S_1[i] = S_2[j])$
上面一条得出了当$S_1[i] = S_2[j]$的计算公式，显然还有另一种情况就是$S_1[i] ≠ S_2[j]$，$若S_1 = ”abc”, S_2 = ”def”$。$S_1$变换到$S_2$的过程可以“修改”，但还可以通过“插入”、“删除”使得$S_1$变换为$S_2$。

在$S_1$字符串末位插入字符$“f”$，此时$S_1 = ”abcf”，S_2 = ”def”$,此时即$S_1[i] = S_2[j]$的情况，$S_1$变换为$S_2$的编辑距离为$d[4, 3] = d[3, 2]$。所以得出$d[i, j]=d[i, j - 1] + 1$。（$+1$是因为$S_1$新增了$”f”$）
在$S_2$字符串末位插入字符$“c”$，此时$S_1 = ”abc”，S_2 = ”defc”$，此时即$S_1[i] = S[j]$的情况，$S_1$变换为$S_2$的编辑距离为$d[3, 4] = d[2, 3]$。所以得出$d[i, j]=d[i - 1, j] + 1$，实际上这是对$S_1$做了删除。（$+1$是因为$S_2$新增了$”c”）$
将$S_1$字符串末位字符修改为$”f”$，此时$S_1 = ”abf”，S_2 = ”def”$，此时即$S_1[i] = S[j]$的情况，$S_1$变换为$S_2$的编辑距离为$d[3, 3] = d[2, 2]$。所以得出$d[i, j] = d[i – 1, j - 1] + 1$。（$+1$是因为$S_1$修改了$“c”$）

import java.util.Scanner;
class Solution{
    public static void main(String[] args){
        Solution s=new Solution();
        Scanner scan = new Scanner(System.in);
        String input = "";
        if (scan.hasNext()) {
            input = scan.nextLine();
        }
        scan.close();
        String[] array = input.split(",");
        System.out.println(s.dnaDiffer(array[0] , array[1]));
    }

    public int dnaDiffer(String d1, String d2) {
        int m = d1.length();
        int n = d2.length();
        if (m == 0) return n;
        if (n == 0) return m;

        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }
        for (int i = 0; i <= n; i++) {
            dp[0][i] = i;
        }

        for (int i = 1; i <= m; i++) {
            char c1 = d1.charAt(i - 1);
            for (int j = 1; j <= n; j++) {
                char c2 = d2.charAt(j - 1);
                if (c1 == c2) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                }
            }
        }
        return dp[m][n];
    }
}

参考文献

动态规划（1）——字符串的编辑距离