两个字符串间的最短路径问题【华为OD机试】(JAVA&Python&C++&JS题解)

一. 题目-两个字符串间的最短路径问题

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

二.解题思路

这个问题可以通过动态规划来解决。首先，我们可以定义一个二维数组dp，其中dp[i][j]表示从字符串A的前i个字符到字符串B的前j个字符的最短距离。然后，我们可以按照以下规则更新dp数组：

1. 如果str1[i] == str2[j]，则dp[i][j] = dp[i-1][j-1]，表示可以形成一个斜边。
2. 否则，dp[i][j]取dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1]中的最小值，分别对应水平边、垂直边和斜边。

接下来，我们可以通过逐行逐列的方式填充dp数组，最终dp[m][n]就是原点到终点的最短距离。

在上面的代码中，all_dp数组存储了两行的dp数组，交替更新，以避免使用额外的空间。

具体思路可以总结为：

1. 初始化dp[0][j]和dp[i][0]，分别表示空串到字符串B和字符串A到空串的距离。
2. 从dp[1][1]开始，逐行逐列填充dp数组。
3. 根据上述规则更新dp数组。
4. 最终输出dp[m][n]，即原点到终点的最短距离。

这样，通过动态规划的思路，可以高效地解决这个问题。

三.题解代码

Python题解代码

import sys
 
for line in sys.stdin:
    str1, str2 = line.strip().split()
    m = len(str1)
    n = len(str2)
 
    all_dp = [[-1 for _ in range(n+1)],[-1 for _ in range(n+1)]]
    index = 0
    for j in range(n+1):
        all_dp[index][j] = j
    for i in range(m):
        dp = all_dp[index]
        new_dp = all_dp[(index+1)%2]
        new_dp[0] = i+1
        index = 1-index
        for j in range(n):
            new_dp[j+1] = new_dp[j] if new_dp[j]<dp[j+1] else dp[j+1]
            if (str1[i]==str2[j]) and (dp[j]<new_dp[j]):
                new_dp[j+1] = dp[j]
            new_dp[j+1] += 1
 
    print(all_dp[index][-1])
    

JAVA题解代码

import java.util.Scanner;
 
 
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] strArray = scanner.nextLine().split(" ");
 
        String s1 = "o" + strArray[0];
        String s2 = "o" + strArray[1];
 
        char[] arr1 = s1.toCharArray();
        char[] arr2 = s2.toCharArray();
 
        int m = arr1.length;
        int n = arr2.length;
 
        boolean[][] used = new boolean[m][n];
        int[][] dp = new int[m][n];
        for (int i = 1; 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(arr1[i] == arr2[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]);
    }
}

C/C++题解代码

#include <iostream>
#include <vector>
#include <set>
#include <queue>

using namespace std;

int main() {
    string s1, s2;
    cin >> s1 >> s2;
    int n = s1.length();
    int m = s2.length();

    // 使用哈希表的数组存储每个点是否访问过
    vector<set<int>> f(n + 1);

    queue<vector<int>> q;
    q.push({-1, -1, 0}); // 初始状态：两个指针位置都为-1，步数为0

    int ans = 1e9; // 初始答案为一个较大的数

    while (!q.empty()) {
        vector<int> t = q.front();
        q.pop(); // 取出队列中的当前状态

        if (t[0] == n - 1) { // 如果指针1已经到达s1的末尾
            ans = min(ans, t[2] + m - t[1] - 1); // 更新答案，加上指针2剩余的步数
            continue;
        }

        if (t[1] == m - 1) { // 如果指针2已经到达s2的末尾
            ans = min(ans, t[2] + n - t[0] - 1); // 更新答案，加上指针1剩余的步数
            continue;
        }

        if (s1[t[0] + 1] == s2[t[1] + 1]) { // 如果指针1和指针2指向的字符相等
            if (f[t[0] + 2].count(t[1] + 1) == 0) { // 如果下一个状态未被访问过
                f[t[0] + 2].insert(t[1] + 1); // 标记为已访问
                q.push({t[0] + 1, t[1] + 1, t[2] + 1}); // 加入队列
            }
        } else { // 如果指针1和指针2指向的字符不相等
            if (f[t[0] + 2].count(t[1]) == 0) { // 如果斜向下走的下一个状态未被访问过
                f[t[0] + 2].insert(t[1]); // 标记为已访问
                q.push({t[0] + 1, t[1], t[2] + 1}); // 加入队列
            }

            if (f[t[0] + 1].count(t[1] + 1) == 0) { // 如果直着走的下一个状态未被访问过
                f[t[0] + 1].insert(t[1] + 1); // 标记为已访问
                q.push({t[0], t[1] + 1, t[2] + 1}); // 加入队列
            }
        }
    }

    cout << ans << endl; // 输出结果

    return 0;
}

JS题解代码

// 导入readline模块
const readline = require('readline');
// 创建readline接口
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

// 当接收到输入时触发回调函数
rl.on('line', (input) => {
    // 将输入的字符串按空格分割为数组
    const [s1, s2] = input.split(' ');
    // 获取字符串s1和s2的长度
    const n = s1.length;
    const m = s2.length;

    // 初始化一个数组来存储已访问的点
    const f = new Array(n + 1);
    for (let i = 0; i <= n; i++) {
        f[i] = new Set();
    }

    // 初始化一个队列，初始状态：两个指针位置都为-1，步数为0
    const q = [];
    q.push([-1, -1, 0]);

    // 初始化答案为一个较大的数
    let ans = Infinity;

    // 进行广度优先搜索
    while (q.length > 0) {
        // 从队列中取出当前状态
        const t = q.shift();
        if (t[0] === n - 1) {
            // 如果指针1已经到达s1的末尾，更新答案，加上指针2剩余的步数
            ans = Math.min(ans, t[2] + m - t[1] - 1);
            continue;
        }
        if (t[1] === m - 1) {
            // 如果指针2已经到达s2的末尾，更新答案，加上指针1剩余的步数
            ans = Math.min(ans, t[2] + n - t[0] - 1);
            continue;
        }
        if (s1[t[0] + 1] === s2[t[1] + 1]) {
            // 如果指针1和指针2指向的字符相等
            if (!f[t[0] + 2].has(t[1] + 1)) {
                // 如果下一个状态未被访问过，标记为已访问，加入队列
                f[t[0] + 2].add(t[1] + 1);
                q.push([t[0] + 1, t[1] + 1, t[2] + 1]);
            }
        } else {
            // 如果指针1和指针2指向的字符不相等
            if (!f[t[0] + 2].has(t[1])) {
                // 如果斜向下走的下一个状态未被访问过，标记为已访问，加入队列
                f[t[0] + 2].add(t[1]);
                q.push([t[0] + 1, t[1], t[2] + 1]);
            }
            if (!f[t[0] + 1].has(t[1] + 1)) {
                // 如果直着走的下一个状态未被访问过，标记为已访问，加入队列
                f[t[0] + 1].add(t[1] + 1);
                q.push([t[0], t[1] + 1, t[2] + 1]);
            }
        }
    }

    // 输出结果
    console.log(ans);
});

代码OJ评判结果
通过测试点

四.代码讲解(Java&Python&C++&JS分别讲解)

Python题解代码解析：

1. 输入处理：

   • 使用sys.stdin从标准输入中读取数据，通过for line in sys.stdin逐行读取输入。
   • line.strip().split()将每行去除首尾空格并按空格分割，得到两个字符串str1和str2。

2. 初始化：

   • 获取字符串str1和str2的长度分别赋给变量m和n。
   • 初始化all_dp为一个包含两个子数组的列表，每个子数组长度为n+1，初始值为-1。

3. 动态规划更新：

   • 外层循环遍历字符串A的每个字符，内层循环遍历字符串B的每个字符。
   • 使用index变量来轮流更新all_dp的两个子数组。
   • 更新new_dp数组的第一个元素为i+1，表示从空串到字符串A的前i个字符的距离。

4. 状态转移方程：

   • 根据动态规划的思想，更新new_dp[j+1]的值，考虑水平边、垂直边和斜边的情况。
   • 若str1[i] == str2[j]，则可以形成一个斜边，使用状态转移方程更新new_dp[j+1]。
   • 最后输出all_dp[index][-1]，即原点到终点的最短距离。

JAVA题解代码解析：

1. 输入处理：

   • 使用Scanner类从标准输入中读取数据，通过scanner.nextLine().split(" ")获取两个字符串strArray。
   • 将字符串A和B的头部添加字符’o’，并转换为字符数组arr1和arr2。

2. 初始化：

   • 获取字符数组arr1和arr2的长度，分别赋给变量m和n。
   • 初始化二维数组dp和布尔数组used，其中dp[i][j]表示从字符串A的前i个字符到字符串B的前j个字符的最短距离。

3. 动态规划更新：

   • 使用两层嵌套循环遍历字符数组arr1和arr2，根据字符是否相等更新dp[i][j]的值。
   • 最终输出dp[m - 1][n - 1]，即原点到终点的最短距离。

C/C++题解代码解析：

1. 输入处理：

   • 使用cin从标准输入读取两个字符串str1和str2。

2. 初始化：

   • 获取字符串str1和str2的长度分别赋给变量n和m。
   • 使用哈希表的数组f来存储每个点是否访问过，初始化为vector<set<int>>。

3. 广度优先搜索：

   • 使用队列q进行广度优先搜索，初始状态包括两个指针位置都为-1，步数为0。
   • 循环中判断当前状态是否满足到达字符串A或B的末尾，更新答案。
   • 根据字符是否相等，更新下一个状态的位置，标记已访问的点，并将新状态加入队列。

4. 输出结果：

   • 输出最终答案。

JS题解代码解析：

1. 输入处理：

   • 使用Node.js的readline模块，通过rl.on('line', (input) => {...}监听每行输入。
   • 将输入的字符串按空格分割为数组strArray，得到两个字符串str1和str2。

2. 初始化：

   • 获取字符串str1和str2的长度分别赋给变量n和m。
   • 初始化一个数组f来存储已访问的点。

3. 广度优先搜索：

   • 使用队列q进行广度优先搜索，初始状态包括两个指针位置都为-1，步数为0。
   • 循环中判断当前状态是否满足到达字符串A或B的末尾，更新答案。
   • 根据字符是否相等，更新下一个状态的位置，标记已访问的点，并将新状态加入队列。

4. 输出结果：

   • 输出最终答案。

寄语