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

off999 2025-06-04 00:37 29 浏览 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给你都下载了

全网最简单易懂!495页Python漫画教程，高清PDF版免费下载

Python 3.14 的 UUIDv6/v7/v8 上新，别再用 uuid4 () 啦!

飞牛NAS部署TVGate Docker项目，实现内网一键转发、代理、jx

python入门到脱坑输入与输出—str()函数

宝塔面板如何添加免费waf防火墙?（宝塔面板开启https）

Python三目运算基础与进阶_python三目运算符判断三个变量

(新版)Python 分布式爬虫与 JS 逆向进阶实战吾爱分享

失业程序员复习python笔记——条件与循环

系统u盘安装（win11系统u盘安装）

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

相关推荐

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

抖音上好看的小姐姐，Python给你都下载了

全网最简单易懂!495页Python漫画教程，高清PDF版免费下载

Python 3.14 的 UUIDv6/v7/v8 上新，别再用 uuid4 () 啦!

飞牛NAS部署TVGate Docker项目，实现内网一键转发、代理、jx

python入门到脱坑 输入与输出—str()函数

宝塔面板如何添加免费waf防火墙?（宝塔面板开启https）

Python三目运算基础与进阶_python三目运算符判断三个变量

(新版)Python 分布式爬虫与 JS 逆向进阶实战吾爱分享

失业程序员复习python笔记——条件与循环

系统u盘安装（win11系统u盘安装）

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

python入门到脱坑输入与输出—str()函数