15. 最少前缀操作问题问题描述

给定两个字符串 SSS 和 TTT，我们需要通过对 SSS 进行若干次操作，使其变成 TTT 的前缀。操作有两种类型：

修改操作：可以修改 SSS 中任意一个字符，使其变为 TTT 对应位置的字符。删除操作：可以删除 SSS 中末尾的字符，直到 SSS 的长度小于或等于 TTT 的长度。

要求计算出最少需要多少次操作才能将 SSS 转换为 TTT 的前缀。

思路解析1. 理解前缀匹配

首先，什么是前缀？前缀是指一个字符串的开头部分。例如，字符串 "abc" 的前缀包括：""（空字符串）、"a"、"ab" 和 "abc"。题目要求的是将字符串 SSS 变成 TTT 的前缀，这意味着我们只需要保留 SSS 的前缀部分，使其与 TTT 一致，并删除 SSS 中多余的字符或修改不匹配的字符。

2. 确定最大公共前缀

要实现这个目标，我们首先需要找到 SSS 和 TTT 的最大公共前缀。这个前缀是 SSS 和 TTT 从左到右相同的部分。任何不属于这个公共前缀的部分都需要进行操作。

举个例子，假设：

那么它们的最大公共前缀就是 "ab"，后面的 "cd" 和 "ef" 需要进行操作。后面我们就需要分析如何最少地进行修改或删除操作。

3. 修改和删除操作4. 优化思路

为了求得最少的操作次数，我们可以分成两步来计算：

找到最大公共前缀的长度。对于公共前缀之后的部分，分别进行修改操作和删除操作。

具体操作的次数就可以通过以下方式计算：

解题步骤计算最大公共前缀长度：从 SSS 和 TTT 的开头开始比较，直到遇到第一个不相同的字符或者任意一个字符串结束。修改操作：对于不匹配的字符，每次操作可以修改 SSS 中的字符，使其与 TTT 对应位置的字符一致。删除操作：如果 SSS 的长度超过 TTT，则需要删除 SSS 中的多余字符。返回操作次数：将修改操作和删除操作的次数加起来即为最少的操作次数。代码实现

def solution(S: str, T: str) -> int:
    # 找到S和T的最大公共前缀长度
    common_prefix_length = 0
    while common_prefix_length < len(S) and common_prefix_length < len(T) and S[common_prefix_length] == T[common_prefix_length]:
        common_prefix_length += 1

    
    # 修改操作：S中与T不匹配的字符
    modify_operations = sum(1 for i in range(common_prefix_length, len(T)) if S[i] != T[i])
    
    # 删除操作：删除S末尾多余的字符
    delete_operations = len(S) - common_prefix_length
    
    # 返回修改和删除操作的总数
    return modify_operations + delete_operations
# 测试用例
if __name__ == '__main__':
    print(solution("aba", "abb"))  # 1 (修改S的第三个字符)
    print(solution("abcd", "efg"))  # 4 (修改前缀并删除多余字符)
    print(solution("xyz", "xy"))  # 1 (删除S的第三个字符)
    print(solution("hello", "helloworld"))  # 0 (已经是前缀)
    print(solution("same", "same"))  # 0 (已经是前缀)

复杂度分析空间复杂度：O(1)O(1)O(1)