两个字符串间的最短路径问题 (100%用例)C卷 (Java&&Python&&Node.js&&C语言&&C++)

2023-12-29 13:48:15

给定两个字符串,分别为字符串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

输出描述:

 

原点到终点的最短距离

示例1 输入输出示例仅供调试,后台判题数据一般不包含示例

输入

ABC ABC

输出

3

示例2 输入输出示例仅供调试,后台判题数据一般不包含示例

输入

ABCABBA CBABAC

输出

9

此题采用动态规划的思想实现,跟网上队列操作不一样,不会出现时间复杂度过大问题。

Java版本

import java.util.Scanner;

public class Main{

    public static int get

文章来源:https://blog.csdn.net/qq_43662348/article/details/135285509
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。