当前位置：首页 > article >正文

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

article 2024/10/20 13:22:41

示例1
输入：
ABC ABC
输出：
3

	A	B	C
A	1
B		1
C			1

示例2
输入：
ABCABBA CBABAC
输出：
9

	A	B	C	A	B	B	A
C
B		1			1	1
A	1			1			1
B		1			1	1
A	1			1			1
C			1

解题思路
1. 最长路线为两段直线之和，即str1+str2长度
2. 变数在于：相同的坐标直连会减小距离
3. 要求出所有可能得路线距离，取得最小值

动态规划：
定义一个二维数组 dp，其中 dp[i][j] 表示从字符串A的前i个字符到字符串B的前j个字符的最短距离。
按照以下规则更新 dp 数组:

初始化dp[0][j]和dp[i][0] ,分别表示空串到字符串B和字符串A到空串的距离。
从dp[1][1] 开始，逐行逐列填充 dp 数组。
- 如果str1[i] == str2[j]，则 dp[i][j]到dp[i-1][j-1] 表示可以形成一个斜边。dp[i][j]取dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1]中的最小值，分别对应水平边、垂直边和斜边。
- 否则, dp[i][j]取dp[i-1][j]、dp[i][j-1]中的最小值，分别对应水平边、垂直边。
通过逐行逐列的方式填充 dp 数组, 最终 dp[m][n]就是原点到终点的最短距离。

import java.util.Scanner;

public class 给定两个字符串间最短路径 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str1 = "0" + in.next();
        String str2 = "0" + in.next();

        int m = str1.length();
        int n = str2.length();
        int[][] dp = new int[m][n];
        for (int i = 0; i < n; i++) {
            dp[0][i] = i;
        }
        for (int i = 0; i < m; i++) {
            dp[i][0] = i;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (str1.charAt(i) == str2.charAt(j)) {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1;
                }
            }
        }
        System.out.println(dp[m - 1][n - 1]);
    }
}