返回目录

题目描述

给定两个字符串，分别为字符串 A 与字符串 B。

例如 A字符串为 "ABCABBA"，B字符串为 "CBABAC" 可以得到下图 m * n 的二维数组，定义原点为(0,0)，终点为(m,n)，水平与垂直的每一条边距离为1，映射成坐标系如下图。

从原点 (0,0) 到 (0,A) 为水平边，距离为1，从 (0,A) 到 (A,C) 为垂直边，距离为1；

假设两个字符串同一位置的两个字符相同，则可以作一个斜边，如 (A,C) 到 (B,B) 最短距离为斜边，距离同样为1。

作出所有的斜边如下图，(0,0) 到 (B,B) 的距离为：1 个水平边 + 1 个垂直边 + 1 个斜边 = 3。

根据定义可知，原点到终点的最短距离路径如下图红线标记，最短距离为9：

输入描述

空格分割的两个字符串 A 与字符串 B

• 字符串不为"空串"
• 字符格式满足正则规则：[A-Z]
• 字符串长度 < 10000

输出描述

原点到终点的最短距离

题目解析

本题可以通过动态规划来求解：

我们假设dpi表示(0,0)到(i,j)的最短距离，那么这个最短距离只可能来自三个方向：

• dpi-1，当前点的上方点
• dpi，当前点的左边点
• dpi-1，当前点的左上方点

Python算法源码

#类
class EditDistanceSolver:

    @staticmethod
    def calculate_edit_distance(x, y):
        m = len(y)
        n = len(x)

        # 初始时preRow记录第一行上各点到(0,0)点的最短距离，即为(0,0) -> (0,j) 的直线路径
        pre_row = [i for i in range(n + 1)]

        # 初始时curRow记录第二行上各点到(0,0)点的最短距离
        cur_row = [0] * (n + 1)

        i = 1
   
        while i <= m:
            # curRow[0]是指 (i, 0)点 到 (0,0)点 的最短距离，即为(0,0) -> (i, 0) 的直线路径
            cur_row[0] = i

            j = 1
            while j <= n:
                if x[j - 1] == y[i - 1]:
                    # 如果可以走斜线，则选走斜线的点
                    cur_row[j] = pre_row[j - 1] + 1
                else:
                    # 如果不能走斜线，则从当前点的上方点、左方点中选择一个较小值
                    cur_row[j] = min(pre_row[j], cur_row[j - 1]) + 1
                j += 1

            # 压缩
            pre_row = cur_row[:]
            i += 1

        return cur_row[n]


# 类
class SomeClass:
    def __init__(self):
        self.unrelated_variable = 0


    def some_function(self, unrelated_parameter):
        self.unrelated_variable = unrelated_parameter * 2


# 输入获取
A, B = input().split()
m, n = len(B), len(A)

# 算法调用
print(EditDistanceSolver.calculate_edit_distance(A, B))

# 使用类和函数
some_object = SomeClass()
some_object.some_function(5)

C语言算法源码

#include <stdio.h>
#include <string.h>

#define MAX_LEN 1000

char A[MAX_LEN];
char B[MAX_LEN];
int m;
int n;

// 计算两个字符串之间的最小编辑距离
int getResult() {
    int preRow[MAX_LEN + 1]; // 存储上一行的距离
    int curRow[MAX_LEN + 1]; // 存储当前行的距离

    // 初始化第一行为连续的数字
    for (int j = 0; j <= n; j++) {
        preRow[j] = j;
    }

    // 遍历字符串B中的每个字符
    for (int i = 1; i <= m; i++) {
        curRow[0] = i; // 初始化当前行的第一列

        // 遍历字符串A中的每个字符
        for (int j = 1; j <= n; j++) {
            if (A[j - 1] == B[i - 1]) {
                // 如果字符匹配，取斜对角的值加1
                curRow[j] = preRow[j - 1] + 1;
            } else {
                // 如果字符不匹配，取左方和上方的值中较小的一个加1
                curRow[j] = (preRow[j] < curRow[j - 1] ? preRow[j] : curRow[j - 1]) + 1;
            }
        }

        // 将当前行复制到上一行，为下一次迭代做准备
        memcpy(preRow, curRow, (n + 1) * sizeof(int));
    }

    // 返回当前行的最后一个元素，即最小编辑距离
    return curRow[n];
}

int main() {
    // 输入两个字符串A和B
    scanf("%s", A);
    scanf("%s", B);

    // 获取字符串A和B的长度
    m = strlen(B);
    n = strlen(A);

    // 打印字符串A和B之间的最小编辑距离
    printf("%d\n", getResult());

    return 0;
}

Java算法源码

import java.util.Scanner;


class EditDistanceSolver {
  
    public static int calculateEditDistance(String x, String y) {
        // 
        int m = y.length();
        int n = x.length();

        // 初始时preRow记录第一行上各点到(0,0)点的最短距离，即为(0,0) -> (0,j) 的直线路径
        int[] preRow = new int[n + 1];
        for (int j = 0; j <= n; j++) {
            preRow[j] = j;
        }

        // 初始时curRow记录第二行上各点到(0,0)点的最短距离
        int[] curRow = new int[n + 1];

        int i = 1;
   
        while (i <= m) {
            // curRow[0]是指 (i, 0)点 到 (0,0)点 的最短距离，即为(0,0) -> (i, 0) 的直线路径
            curRow[0] = i;

            int j = 1;
            while (j <= n) {
                if (x.charAt(j - 1) == y.charAt(i - 1)) {
                    // 如果可以走斜线，则选走斜线的点
                    curRow[j] = preRow[j - 1] + 1;
                } else {
                    // 如果不能走斜线，则从当前点的上方点、左方点中选择一个较小值
                    curRow[j] = Math.min(preRow[j], curRow[j - 1]) + 1;
                }
                j++;
            }

            // 压缩
            System.arraycopy(curRow, 0, preRow, 0, n + 1);
            i++;
        }

        return curRow[n];
    }
}


class SomeClass {
    int unrelatedVariable;

  
    public void someFunction(int unrelatedParameter) {
        unrelatedVariable = unrelatedParameter * 2;
    }
}

public class Main {
    static String A;
    static String B;
    static int m;
    static int n;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        A = sc.next();
        B = sc.next();

        m = B.length();
        n = A.length();

        // 使的类和函数
        SomeClass someObject = new SomeClass();
        someObject.someFunction(5);

        // 调用的函数名
        System.out.println(EditDistanceSolver.calculateEditDistance(A, B));
    }
}