刷题笔记合集🔗

问题描述

小兰在研究字符串编辑距离时，发现了一个有趣的问题。给定两个字符串A和B，需要找到从原点(0,0)到终点(m,n)的最短路径。

路径规则如下:

• 水平和垂直移动距离为1
• 当两个字符串对应位置字符相同时，可以走斜线，距离也为1
• 需要找到从原点到终点的最短路径长度

例如，对于字符串A="ABCABBA"和B="CBABAC":

• 从(0,0)到(0,A)是水平边，距离为1
• 从(0,A)到(A,C)是垂直边，距离为1
• 当字符相同时可以走斜边，如(A,C)到(B,B)，距离为1

输入格式

输入一行，包含两个由空格分隔的字符串A和B。

输出格式

输出一个整数，表示从原点到终点的最短路径长度。

样例输入1

ABC ABC

样例输出1

3

样例输入2

ABCABBA CBABAC

样例输出2

9

数据范围

• 字符串不为空
• 字符串只包含大写字母[A-Z]
• 字符串长度 < 10000

题解

这是一个动态规划问题，主要思路如下：

1. 状态定义

• dp[i][j]表示从(0,0)到(i,j)的最短路径长度
• i和j分别表示字符串B和A的位置

2. 状态转移

• 当A[j-1] == B[i-1]时，可以走斜线
  • dp[i][j] = dp[i-1][j-1] + 1
• 否则，只能从上方或左方到达
  • dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1

3. 初始化

• 第一行：dp[0][j] = j
• 第一列：dp[i][0] = i

4. 优化

• 由于只需要前一行的数据，可以使用滚动数组优化空间复杂度

时间复杂度：O(mn)，其中m和n是两个字符串的长度。 空间复杂度：O(n)，使用滚动数组优化后。

参考代码

def solve(A, B):
    """
    A, B: 输入的两个字符串
    return: 最短路径长度
    """
    m, n = len(B), len(A)
    
    # 初始化前一行
    pre_row = list(range(n + 1))
    # 当前行
    cur_row = [0] * (n + 1)
    
    # 逐行计算
    for i in range(1, m + 1):
        # 第一列初始化
        cur_row[0] = i
        
        # 计算当前行的值
        for j in range(1, n + 1):
            if A[j-1] == B[i-1]:
                # 字符相同，可以走斜线
                cur_row[j] = pre_row[j-1] + 1
            else:
                # 字符不同，取上方或左方的较小值
                cur_row[j] = min(pre_row[j], cur_row[j-1]) + 1
        
        # 更新前一行
        pre_row = cur_row[:]
    
    return cur_row[n]

# 读取输入
A, B = input().split()
# 输出结果
print(solve(A, B))

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // 计算最短路径长度
    int solve(const string& A, const st