【华为OD机试真题2023C&D卷 JAVA&JS】两个字符串间的最短路径问题

2023-12-23 22:37:12

华为OD2023(C&D卷)机试题库全覆盖,刷题指南点这里

两个字符串间的最短路径问题

知识点数组动态规划字符串

时间限制:1s 空间限制:256MB 限定语言:不限

题目描述:

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

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