Python 实现【找出经过特定点的路径长度】

off999 2025-06-04 00:37 15 浏览 0 评论

def min_distance():
    # 读取输入
    s = input().strip()
    required = input().strip()
    
    # 创建一个字典来存储每个字符的所有出现位置
    from collections import defaultdict
    char_positions = defaultdict(list)
    for idx, char in enumerate(s):
        char_positions[char].append(idx)
    
    # 检查所有必过字符是否都存在
    for char in required:
        if char not in char_positions:
            print(-1)
            return
    
    # 动态规划表，dp[i][j]表示处理到required的第i个字符时，位于s的第j个位置的最小总距离
    # 初始化处理第一个字符的所有可能位置
    dp = []
    first_char = required[0]
    for pos in char_positions[first_char]:
        dp.append((pos, 0))  # (current position, total distance)
    
    for i in range(1, len(required)):
        current_char = required[i]
        next_dp = []
        for pos in char_positions[current_char]:
            min_dist = float('inf')
            for prev_pos, prev_dist in dp:
                # 计算从prev_pos到pos的距离
                dist = abs(pos - prev_pos)
                if prev_dist + dist < min_dist:
                    min_dist = prev_dist + dist
            next_dp.append((pos, min_dist))
        dp = next_dp
    
    # 找出所有可能位置中的最小总距离
    if not dp:
        print(-1)
    else:
        min_total = min(dist for pos, dist in dp)
        print(min_total)

min_distance()

关键步骤：

字母位置记录：首先记录每个字母在字符串中的位置（索引），因为同一个字母可能出现多次。
必过点处理：处理必过的点，确定每个必过点的字母在字符串中的位置。
动态规划计算最小距离：使用动态规划来计算从一个必过点到下一个必过点的最小距离。动态规划的状态可以表示为当前所在的字母位置，以及已经经过的必过点数量。

python字符串长度

上一篇：python 字符串的定义和表示（python中字符串的定义）
下一篇：Python 随机字符串（python中随机选取字符）

Python 实现【找出经过特定点的路径长度】

相关推荐

取消回复欢迎你发表评论:

编写一个自动生成双色球号码的 Python 小脚本

折线图怎么设置横坐标和纵坐标（折线图怎么设置横坐标和纵坐标单位）

5分钟掌握Python(五)之匿名函数（python中的匿名函数）

推荐一款好用的国产桌面软件开发工具Aardio

Python基础编程——赋值语句的高级用法

怎么批量修改视频文件名?8个方法教你轻松应对

有了这个Python库，免费实现验证码识别!

一文彻底搞懂命令行参数设计规范（命令行参数是什么函数的参数）

Python实现WebService接口(SOAP)（python webservice接口）

Windows“任务计划程序”定时执行bat脚本

Python 实现【找出经过特定点的路径长度】

相关推荐

取消回复欢迎 你 发表评论:

编写一个自动生成双色球号码的 Python 小脚本

折线图怎么设置横坐标和纵坐标（折线图怎么设置横坐标和纵坐标单位）

5分钟掌握Python(五)之匿名函数（python中的匿名函数）

推荐一款好用的国产桌面软件开发工具Aardio

Python基础编程——赋值语句的高级用法

怎么批量修改视频文件名?8个方法教你轻松应对

有了这个Python库，免费实现验证码识别!

一文彻底搞懂命令行参数设计规范（命令行参数是什么函数的参数）

Python实现WebService接口(SOAP)（python webservice接口）

Windows“任务计划程序”定时执行bat脚本

取消回复欢迎你发表评论: