本文主要是介绍华为od-C卷200分题目3 - 两个字符串间的最短路径问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
华为od-C卷200分题目3 - 两个字符串间的最短路径问题
题目描述
给定两个字符串,分别为字符串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
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);String s = sc.nextLine();String[] str = s.split(" ");int n = str[0].length();int m = str[1].length();int[][] nums = new int[n + 1][m + 1];for (int i = 1; i <= n; i++) {nums[i][0] = i;}for (int i = 1; i <= m; i++) {nums[0][i] = i;}for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {nums[i][j] = Math.min(nums[i][j - 1], nums[i - 1][j]) + 1;if (str[0].charAt(i - 1) == str[1].charAt(j - 1)) {nums[i][j] = Math.min(nums[i][j], nums[i - 1][j - 1] + 1);}}}System.out.println(nums[n][m]);}
}
思路:动态规划,当前位置的最小值取决于前一步,要么是上要么是左,如果当前字符相同则可以走斜线,左上角的位置
这篇关于华为od-C卷200分题目3 - 两个字符串间的最短路径问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!