合并字符串形成目标串的最小插入成本问题

题目描述
给定两个字符串s和t，以及三个整数costInsert、costDelete和costReplace，分别表示插入、删除和替换一个字符的成本。你可以对字符串s执行以下三种操作任意次数：

1. 插入任意字符到任意位置，每次插入成本为costInsert
2. 删除任意字符，每次删除成本为costDelete
3. 替换任意字符为另一个字符，每次替换成本为costReplace

请计算将字符串s转换为字符串t的最小总成本。

示例
输入：s = "horse", t = "ros", costInsert = 1, costDelete = 1, costReplace = 1
输出：3
解释：将s转换为t的最小成本为3：

• 删除'h' (成本1)
• 将'r'替换为'o' (成本1)
• 删除'e' (成本1)

解题过程

步骤1：理解问题本质
这是一个经典的编辑距离问题的扩展版本，不同之处在于三种操作的成本可以不同。我们需要找到从s转换到t的成本最低的操作序列。

步骤2：定义状态
定义dp[i][j]表示将s的前i个字符转换为t的前j个字符的最小成本。

• 当i=0时，表示s是空字符串，需要通过插入操作得到t的前j个字符
• 当j=0时，表示t是空字符串，需要通过删除操作清空s的前i个字符

步骤3：状态转移方程

对于每个位置(i,j)，考虑三种可能的操作：

1. 删除操作：删除s的第i个字符，然后考虑将s的前i-1个字符转换为t的前j个字符

   • 成本 = dp[i-1][j] + costDelete

2. 插入操作：在s的第i个位置后插入t的第j个字符，然后考虑将s的前i个字符转换为t的前j-1个字符

   • 成本 = dp[i][j-1] + costInsert

3. 替换操作：

   • 如果s[i-1] == t[j-1]：字符相同，不需要替换，成本 = dp[i-1][j-1]
   • 如果s[i-1] != t[j-1]：需要替换，成本 = dp[i-1][j-1] + costReplace

状态转移方程：

dp[i][j] = min(
    dp[i-1][j] + costDelete,           // 删除s[i-1]
    dp[i][j-1] + costInsert,           // 插入t[j-1]
    s[i-1] == t[j-1] ? dp[i-1][j-1] : dp[i-1][j-1] + costReplace
)

步骤4：初始化

• dp[0][0] = 0 （两个空字符串相互转换成本为0）
• dp[i][0] = i × costDelete （删除s的前i个字符）
• dp[0][j] = j × costInsert （插入t的前j个字符）

步骤5：计算顺序
按行或按列填充dp表，确保计算dp[i][j]时所需的子问题都已计算完成。

步骤6：示例推导
以s="horse", t="ros"为例，costInsert=costDelete=costReplace=1：

初始化：

dp[0][0]=0, dp[0][1]=1, dp[0][2]=2, dp[0][3]=3
dp[1][0]=1, dp[2][0]=2, dp[3][0]=3, dp[4][0]=4, dp[5][0]=5

计算过程：

• dp[1][1]：'h'→'r'，min(删除1+0=1, 插入1+1=2, 替换1+0=1) = 1
• dp[1][2]：'h'→'ro'，min(删除1+2=3, 插入2+1=3, 替换1+1=2) = 2
• ...
• 最终dp[5][3]=3

步骤7：复杂度分析

• 时间复杂度：O(m×n)，其中m和n分别是字符串s和t的长度
• 空间复杂度：O(m×n)，可以使用滚动数组优化到O(min(m,n))

步骤8：边界情况处理

• 当s和t都为空时，成本为0
• 当s为空t非空时，成本为t.length × costInsert
• 当s非空t为空时，成本为s.length × costDelete
• 当costReplace成本很高时，可能选择删除+插入的组合操作更优

这个算法能够高效地找到将字符串s转换为字符串t的最小成本操作序列，是编辑距离问题的通用解法。