最新华为OD机试真题-两个字符串间的最短路径(200分)

大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解

感谢大家的订阅➕ 和 喜欢

最新华为OD机试D卷目录，全、新、准，题目覆盖率达 95% 以上，支持题目在线评测

最新华为OD机试目录: https://www.nowcoder.com/discuss/636153620743897088?sourceSSR=users

在线评测链接

两个字符串间的最短路径(200分) 评测功能需要 ⇒ 订阅专栏 ⇐ 后私信联系清隆解锁～

评测功能需要 =>订阅专栏<= 后联系清隆解锁～

OJ题目截图

✨ 两个字符串间的最短路径

问题描述

给定两个字符串 和 。例如，字符串 为 "ABCABBA"，字符串 为 "CBABAC"。可以构建一个大小为 的二维数组，其中 为字符串 的长度， 为字符串 的长度。定义二维数组的原点为 ，终点为 。在数组中，水平和垂直的每条边的距离为 1，如果字符串 和字符串 在相同位置的字符相同，则可以画一条斜边，斜边的距离同样为 1。

例如，从 到 是水平边，距离为 1；从 到 是垂直边，距离为 1。如果两个字符串在相同位置的字符相同，例如 到 ，则可以画一条斜边，距离为 1。这样，原点 到终点 的最短路径包括水平边、垂直边和斜边。

输入格式

第一行包含两个用空格分隔的字符串 和 ，字符串不为空，字符格式满足正则规则：[A-Z]，且字符串长度 。

输出格式

输出从原点 到终点 的最短路径距离。

样例输入

输入1

ABC ABC

输入2

ABCABBA CBABAC

样例输出

输出1

3

输出2

9

样例解释

对于输入 "ABC" 和 "ABC"，可以画出以下路径：

(0,0) -> (A,0) -> (A,A) -> (B,B) -> (C,C)

对于输入 "ABCABBA" 和 "CBABAC"，最短路径如下图红线标记，最短距离为 9：

(0,0) -> (A,0) -> (A,C) -> (B,B) -> (C,B) -> (A,A) -> (B,B) -> (B,B) -> (A,A) -> (A,C)

数据范围

字符串长度 。

题解

我们可以使用动态规划来解决这个问题。定义一个二维数组 ，其中 表示从原点 到 的最短距离。初始化时，，然后根据以下规则进行状态转移：

1. 如果 ，则 。
2. 如果 ，则 。
3. 如果 且 且 ，则 。

最后， 即为所求的最短路径距离。

参考代码

• Python

def min_distance(A, B):
    m, n = len(A), len(B)
    dp = [[float('inf')] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = 0
    
    for i in range(m + 1):
        for j in range(n + 1):
            if i > 0:
                dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1)
            if j > 0:
                dp[i][j]