两个字符串间的最短路径
2026华为OD机试双机位C卷 - 华为OD上机考试双机位C卷
华为OD机试双机位C卷真题目录点击查看: 【全网首发】2026华为OD机位C卷 机考真题题库含考点说明以及在线OJ（OD上机考试双机位C卷）
题目描述
给定两个字符串，分别为字符串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；
路径为(0,0)->(A,0)->(A,C)->(B,B)->(C,B)->(A,A)->(B,B)->(B,B)->(A,A)->(A,C)
输入描述
空格分割的两个字符串 A 与字符串 B
-
字符串不为"空串"
-
字符格式满足正则规则：[A-Z]
-
字符串长度 < 10000
输出描述
原点到终点的最短距离
用例
| 输入 | ABC ABC |
|---|---|
| 输出 | 3 |
| 说明 | 无 |
| 输入 | ABCABBA CBABAC |
|---|---|
| 输出 | 9 |
| 说明 | 无 |
解题思路
题意其实很简单，就是把AB两个字符串的字符映射到坐标轴上面。A的字符串为x轴，B的字符串为y轴。
起始和终点为（0,0）和（m,n）。然后求起点到终点的最短路径。这个路径的求法有限制。
如上面的图所示，起点为（0,0），然后下一个坐标轴，可以往（0，A）或者（C,0）走，这里我们选择往（0，A）走。然后再往（A,C）走。然后我们可以往（C,B）或者（B,0）或（B,B）（这个坐标是因为坐标的x和y都为B,所以可以斜着走）走。知道走到终点。
这个问题可以通过动态规划来解决。动态规划的基本思想是将一个复杂的问题分解为多个子问题，然后通过解决子问题来解决原问题。在这个问题中，我们需要找到从原点到终点的最短距离，这个距离可以通过计算到每个点的最短距离来得到。
首先，我们需要创建一个动态规划数组，用于存储到每个点的最短距离。然后，我们初始化数组的第一行和第一列，即从原点到每个点的距离。
接下来，我们遍历字符串B，对于每个字符，我们遍历字符串A，对于每个字符，我们检查当前字符是否与字符串B的当前字符匹配。如果匹配，那么我们更新动态规划数组的当前位置为左上角的值加1；如果不匹配，那么我们更新动态规划数组的当前位置为左边和上边的最小值加1。
最后，我们输出从原点到终点的最短距离，即动态规划数组的最后一个元素。
以下是详细的推导过程：
-
初始化：
dp[0]到dp[n]初始化为0到n，因为从字符串A的开头到每个位置的最短距离就是对应的索引值（即水平移动的距离）。
-
遍历字符串B（
i从1到m）：-
在每次新的行开始时，更新
dp[0]为i，因为从字符串B的开头到当前位置的最短距离就是i（即垂直移动的距离）。 -
保存
prev为左上角的值，即上一行的dp[0]。
-
-
遍历字符串A（
j从1到n）：-
保存
temp为当前dp[j]的值，因为在更新dp[j]时需要用到。 -
如果
A[j-1] == B[i-1]（字符匹配），则dp[j]更新为prev + 1，因为可以直接从左上角移动到当前位置。 -
如果
A[j-1] != B[i-1]（字符不匹配），则dp[j]更新为min(dp[j], dp[j-1]) + 1，即从左边或上边移动到当前位置的最小值加1。 -
更新
prev为当前dp[j]的原始值（即temp）。
-
-
最终，
dp[n]保存了从字符串A到字符串B的最短距离。
这个过程中，我们只保留了当前行和上一行的信息，从而将空间复杂度从O(mn)降低到了O(n)。