计算两字符串间的新增字符数量（支持存在字符删除的场景）

核心逻辑基于最长公共子序列（LCS）实现，LCS指两个字符串中顺序一致、不需要连续的最长公共字符序列，刚好对应两次字符串版本之间没有被删除/修改的保留字符。最终新增字符数计算公式为：
新增字符数 = 变更后字符串总长度 - 两个字符串的LCS长度

Python 实现代码 #

def count_added_chars(original: str, modified: str) -> int:
    m, n = len(original), len(modified)
    # 构建动态规划表，dp[i][j]表示original前i个字符和modified前j个字符的LCS长度
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if original[i-1] == modified[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    
    # 新增字符数 = 变更后长度 - 公共保留长度
    return len(modified) - dp[m][n]

# 测试示例
s1 = "I love Programming so much"
s2 = "I used to love programming"
print(count_added_chars(s1, s2)) # 输出8，和预期一致

可选调整项 #

如果需求认为大小写不同的同一个字符属于匹配项（比如示例中的Programming和programming视为相同），可以在判断字符相等前先统一转成小写/大写：

# 替换字符相等判断逻辑即可
if original[i-1].lower() == modified[j-1].lower():

内容的提问来源于stack exchange，提问作者Yassine Soltani