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

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()

关键步骤：

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