合并相邻字符形成目标串的最小操作次数问题

字数 5074 2025-12-06 02:26:55

合并相邻字符形成目标串的最小操作次数问题

题目描述
给定一个初始字符串 s 和一个目标字符串 t，初始时 s 的每个字符都是独立的块。每次操作可以选择 s 中相邻的两个字符块，将它们合并成一个新块，新块的内容是这两个块中字符按原顺序拼接后的字符串。重复此操作，直到 s 变成一个由若干块组成的序列。问：能否通过这种合并操作，使 s 的最终块序列（按顺序拼接）等于目标字符串 t？如果能够做到，返回所需的最少合并操作次数；如果无法做到，返回 -1。
例如：

输入：s = "abcde", t = "ab"，无法得到 t（t 比 s 短，且不能拆分 t），返回 -1。
输入：s = "abc", t = "abc"，无需合并，返回 0。
输入：s = "abcde", t = "ab cde"（这里空格仅为视觉分隔），可以先将 "abcde" 分为 ["ab", "cde"]，需要 1 次合并（合并 "a" 和 "b" 成 "ab"，其余不动）。
实际上，t 是一个目标串，我们需要判断 s 能否被划分成若干连续子串，使得按顺序拼接后等于 t，且每个子串是 s 的一段连续子串（即通过合并相邻块形成），目标是让合并次数最少。

解题思路
这道题可以转化为：在 s 中找到一个划分，将其划分为 k 个连续非空子串，依次对应 t 的 k 个部分，且这 k 个子串顺序拼接后正好是 s 本身（即划分覆盖整个 s）。
定义 dp[i][j] 表示考虑 s 的前 i 个字符（长度 i）匹配到 t 的前 j 个字符（长度 j）所需的最少合并次数，如果无法匹配则为无穷大。
最终答案是 dp[n][m]，其中 n = len(s), m = len(t)。
如果 n < m 或 s 的字符集合与 t 不一致（但需按顺序匹配），则直接不可能。

状态转移：
当我们尝试匹配 t 的前 j 个字符，且最后一个匹配块对应 t 的某一段 t[l:j]（l 是上一个块结束的下一个位置，0 ≤ l < j），这段必须在 s 中对应一段连续的字符，且与 t[l:j] 相等。
反过来推：假设 dp[i][j] 已知，我们想从 s 的前 i 个字符中匹配 t 的前 j 个字符，那么最后一个块一定是 s[p:i] 对应 t[q:j] 且 s[p:i] == t[q:j]，且 dp[p][q] 是之前的最优解。
但这样不方便直接递推。更好方法是：
定义 dp[i][j] 表示 s[0:i] 匹配 t[0:j] 的最少合并次数。
转移时，我们枚举最后一个块在 s 中的起始位置 k（0 ≤ k < i），使得 s[k:i] 正好等于 t[? : j] 的一段。这里需要知道 t 中对应段的长度是 i-k，设该段在 t 中的结束位置是 j，则起始位置是 j - (i-k)。
因此，s[k:i] 必须等于 t[j-(i-k) : j]。
如果相等，则 dp[i][j] = min(dp[i][j], dp[k][j-(i-k)] + (i-k-1))。
这里 (i-k-1) 是将 s[k:i] 这段字符（长度 L=i-k）从初始的 L 个单字符块合并成 1 块需要的合并次数 = L-1。
注意：dp[0][0] = 0（空串匹配空串）。

初始条件：
dp[i][j] = INF（很大数），dp[0][0] = 0。
如果 s[0] == t[0]，则 dp[1][1] = 0（单字符直接匹配，无需合并）。

最终结果：
如果 dp[n][m] 是 INF，则返回 -1，否则返回 dp[n][m]。

逐步推演
例：s = "abcde", t = "ab cde"（m=5 同 n=5）。

初始化 dp[5+1][5+1] 全 INF，dp[0][0] = 0。
遍历 i=1..n, j=1..m，但注意 i 和 j 的关系必须满足 s 的前 i 个字符能匹配 t 的前 j 个字符。
实际上我们遍历最后一个块的起始位置 k 从 0 到 i-1，长度 len = i-k，在 t 中对应 t[j-len : j]，需要 j >= len 且子串相等。
对 i=2, j=2：
- 尝试 k=0, len=2, t[0:2]="ab", s[0:2]="ab" 相等，则 dp[2][2] = dp[0][0] + (2-1) = 0 + 1 = 1。
- 尝试 k=1, len=1, t[1:2]="b", s[1:2]="b" 相等，则 dp[2][2] = min(INF, dp[1][1] + 0)，需先有 dp[1][1]。
  先算 i=1,j=1：k=0,len=1，s[0]="a", t[0]="a" 相等，dp[1][1] = dp[0][0] + 0 = 0。
  所以 dp[2][2] 还可以是 0+0=0？等一下，这里注意：k=1 时，t 对应起始是 j-len = 2-1=1，即 t[1:2]="b"，s[1:2]="b" 相等，dp[1][1]=0 表示 s[0:1] 匹配 t[0:1]，但现在是 s[1:2] 匹配 t[1:2]，所以前一段是 s[0:1] 匹配 t[0:1]，合并成 [a][b] 两个块，不需合并。确实 dp[2][2]=0 是更优的，表示不合并直接两个单字符块。题目要求总合并次数最少，所以 dp[2][2]=0。
继续算到 i=5, j=5：
考虑最后一个块可能是 s[2:5]="cde" 对应 t[2:5]="cde"，len=3，k=2，t 起始位置 j-len=2，dp[2][2]=0，dp[5][5] = dp[2][2] + (3-1) = 0 + 2 = 2。
但还有另一种划分：最后一个块是 s[0:5] 对应整个 t，len=5，dp[0][0]+4=4，更大。
还有可能是最后两个块是 ["ab", "cde"]，对应 t[0:2] 和 t[2:5]。
这已经在 dp[2][2]=0 时，加上 "cde" 合并次数 2，得到 2。
检查是否更小：dp[3][3] 对应 "abc" 匹配 "abc" 时，最后块 "c" 是单个字符，dp[3][3]=0，再加 "de" 合并一次，总共1？不对，那样是 "abc" 与 "de" 合并成 "abcde" 吗？不，我们要整个 s 匹配 t，"ab" 与 "cde" 之间是独立的块，不需要合并这两个大块。
所以最优是 1 次合并（合并 "a" 和 "b" 成 "ab"，"c"、"d"、"e" 不合并或合并成 "cde" 需要 2 次合并）。等等，我们要覆盖整个 s 为 t，t="ab cde" 对应两块，"ab" 需要合并一次（a,b 合并），"cde" 需要合并两次（c,d 合并成 "cd"，再与 "e" 合并成 "cde"），总共 3 次？但这是将 s 变成 ["ab", "cde"] 两个块的过程：初始 [a,b,c,d,e] 五个块，要变成 [ab, cde] 两块，需要合并次数是 5-2=3 次。但我们可以让 "cde" 内部不合并吗？不行，因为 "cde" 是一个块，它必须是由三个单字符块合并两次得到。所以总合并次数=3。
但前面计算 dp[5][5] 时，k=2 对应 "cde" 合并 2 次，加上 "ab" 合并 1 次（在 dp[2][2] 里？），检查 dp[2][2] 是怎么来的：dp[2][2]=0 表示 "ab" 作为两个单字符块，没合并。但实际最终我们需要 "ab" 是一个块，所以合并 1 次应加在 "ab" 这一段上。
所以状态定义需调整：dp[i][j] 表示匹配完后，最后一块是合并好的一个块（即最后一段内部已合并成一个整体），这样转移时，最后一段的合并次数是 len-1 次。
之前公式已体现：dp[i][j] = dp[k][j-len] + (len-1)。
这样 dp[2][2] 表示 s[0:2] 匹配 t[0:2] 且最后是一个块，那必须 k=0 时，len=2，dp[0][0]+1=1，所以 dp[2][2]=1。
则 dp[5][5] 在 k=2 时，len=3，dp[2][2]=1，加上 3-1=2，总 3 次。
这是对的。
再检查 dp[2][2] 能否是 0？如果是 0 表示 "ab" 是两个块，但最后整体匹配 t 时，t[0:2] 是一个块 "ab"，所以不允许最后是两个块，因此必须合并成一块。所以在 dp 定义中，最后一块必须是一个整体块。
这样结果就是最少合并次数 3。

算法步骤总结

如果 len(s) < len(t) 或 s 与 t 的字符集合顺序不一致（但需完全匹配），直接返回 -1（实际在 DP 中不可行会 INF）。
初始化 dp[n+1][m+1] 为 INF，dp[0][0] = 0。
对于每个 i 从 1 到 n，每个 j 从 1 到 m：
- 枚举最后一块长度 len 从 1 到 min(i, j)，令 k = i - len（最后一块在 s 中起始下标）。
- 检查 s[k:i] == t[j-len:j]。
- 如果相等，则 dp[i][j] = min(dp[i][j], dp[k][j-len] + (len-1))。
如果 dp[n][m] 是 INF，返回 -1，否则返回它。

时间复杂度 O(n² m) 可优化到 O(n m) 吗？这里 n 和 m 相等，所以 O(n³)。但实际可优化：因为 len 从 1 到 i，j 需 ≥ len，且子串相等检查可预先哈希加速。

举例验证
s = "abc", t = "abc"，n=m=3。

i=1,j=1：len=1, s[0:1]="a", t[0:1]="a" 相等，dp[1][1] = dp[0][0]+0=0。
i=2,j=2：
- len=1：s[1:2]="b", t[1:2]="b" 相等，dp[2][2]=dp[1][1]+0=0。
- len=2：s[0:2]="ab", t[0:2]="ab" 相等，dp[2][2]=min(0, dp[0][0]+1=1)=0。
i=3,j=3：
- len=1：s[2:3]="c", t[2:3]="c" 相等，dp[3][3]=dp[2][2]+0=0。
- len=2：s[1:3]="bc", t[1:3]="bc" 相等，dp[3][3]=min(0, dp[1][1]+1=1)=0。
- len=3：s[0:3]="abc", t[0:3]="abc" 相等，dp[3][3]=min(0, dp[0][0]+2=2)=0。
  结果 0，正确。

边界与不可行情况
若 s = "abcde", t = "abf"，则 s[2]="c" 对 t[2]="f" 不匹配，所有可能划分都会在某处不相等，最终 dp[n][m] 为 INF，返回 -1。

这样，我们就得到了一个完整的区间 DP 解法。

合并相邻字符形成目标串的最小操作次数问题题目描述给定一个初始字符串 s 和一个目标字符串 t ，初始时 s 的每个字符都是独立的块。每次操作可以选择 s 中相邻的两个字符块，将它们合并成一个新块，新块的内容是这两个块中字符按原顺序拼接后的字符串。重复此操作，直到 s 变成一个由若干块组成的序列。问：能否通过这种合并操作，使 s 的最终块序列（按顺序拼接）等于目标字符串 t ？如果能够做到，返回所需的最少合并操作次数；如果无法做到，返回 -1。例如：输入： s = "abcde" , t = "ab" ，无法得到 t （ t 比 s 短，且不能拆分 t ），返回 -1。输入： s = "abc" , t = "abc" ，无需合并，返回 0。输入： s = "abcde" , t = "ab cde" （这里空格仅为视觉分隔），可以先将 "abcde" 分为 ["ab", "cde"] ，需要 1 次合并（合并 "a" 和 "b" 成 "ab" ，其余不动）。实际上， t 是一个目标串，我们需要判断 s 能否被划分成若干连续子串，使得按顺序拼接后等于 t ，且每个子串是 s 的一段连续子串（即通过合并相邻块形成），目标是让合并次数最少。解题思路这道题可以转化为：在 s 中找到一个划分，将其划分为 k 个连续非空子串，依次对应 t 的 k 个部分，且这 k 个子串顺序拼接后正好是 s 本身（即划分覆盖整个 s ）。定义 dp[i][j] 表示考虑 s 的前 i 个字符（长度 i ）匹配到 t 的前 j 个字符（长度 j ）所需的最少合并次数，如果无法匹配则为无穷大。最终答案是 dp[n][m] ，其中 n = len(s) , m = len(t) 。如果 n < m 或 s 的字符集合与 t 不一致（但需按顺序匹配），则直接不可能。状态转移：当我们尝试匹配 t 的前 j 个字符，且最后一个匹配块对应 t 的某一段 t[l:j] （ l 是上一个块结束的下一个位置， 0 ≤ l < j ），这段必须在 s 中对应一段连续的字符，且与 t[l:j] 相等。反过来推：假设 dp[i][j] 已知，我们想从 s 的前 i 个字符中匹配 t 的前 j 个字符，那么最后一个块一定是 s[p:i] 对应 t[q:j] 且 s[p:i] == t[q:j] ，且 dp[p][q] 是之前的最优解。但这样不方便直接递推。更好方法是：定义 dp[i][j] 表示 s[0:i] 匹配 t[0:j] 的最少合并次数。转移时，我们枚举最后一个块在 s 中的起始位置 k （ 0 ≤ k < i ），使得 s[k:i] 正好等于 t[? : j] 的一段。这里需要知道 t 中对应段的长度是 i-k ，设该段在 t 中的结束位置是 j ，则起始位置是 j - (i-k) 。因此， s[k:i] 必须等于 t[j-(i-k) : j] 。如果相等，则 dp[i][j] = min(dp[i][j], dp[k][j-(i-k)] + (i-k-1)) 。这里 (i-k-1) 是将 s[k:i] 这段字符（长度 L=i-k ）从初始的 L 个单字符块合并成 1 块需要的合并次数 = L-1 。注意： dp[0][0] = 0 （空串匹配空串）。初始条件： dp[i][j] = INF （很大数）， dp[0][0] = 0 。如果 s[0] == t[0] ，则 dp[1][1] = 0 （单字符直接匹配，无需合并）。最终结果：如果 dp[n][m] 是 INF，则返回 -1，否则返回 dp[n][m] 。逐步推演例： s = "abcde" , t = "ab cde" （ m=5 同 n=5 ）。初始化 dp[5+1][5+1] 全 INF， dp[0][0] = 0 。遍历 i=1..n , j=1..m ，但注意 i 和 j 的关系必须满足 s 的前 i 个字符能匹配 t 的前 j 个字符。实际上我们遍历最后一个块的起始位置 k 从 0 到 i-1 ，长度 len = i-k ，在 t 中对应 t[j-len : j] ，需要 j >= len 且子串相等。对 i=2, j=2 ：尝试 k=0 , len=2 , t[0:2]="ab" , s[0:2]="ab" 相等，则 dp[2][2] = dp[0][0] + (2-1) = 0 + 1 = 1 。尝试 k=1 , len=1 , t[1:2]="b" , s[1:2]="b" 相等，则 dp[2][2] = min(INF, dp[1][1] + 0) ，需先有 dp[1][1] 。先算 i=1,j=1 ： k=0,len=1 ， s[0]="a" , t[0]="a" 相等， dp[1][1] = dp[0][0] + 0 = 0 。所以 dp[2][2] 还可以是 0+0=0 ？等一下，这里注意： k=1 时， t 对应起始是 j-len = 2-1=1 ，即 t[1:2]="b" ， s[1:2]="b" 相等， dp[1][1]=0 表示 s[0:1] 匹配 t[0:1] ，但现在是 s[1:2] 匹配 t[1:2] ，所以前一段是 s[0:1] 匹配 t[0:1] ，合并成 [a][b] 两个块，不需合并。确实 dp[2][2]=0 是更优的，表示不合并直接两个单字符块。题目要求总合并次数最少，所以 dp[2][2]=0 。继续算到 i=5, j=5 ：考虑最后一个块可能是 s[2:5]="cde" 对应 t[2:5]="cde" ， len=3 ， k=2 ， t 起始位置 j-len=2 ， dp[2][2]=0 ， dp[5][5] = dp[2][2] + (3-1) = 0 + 2 = 2 。但还有另一种划分：最后一个块是 s[0:5] 对应整个 t ， len=5 ， dp[0][0]+4=4 ，更大。还有可能是最后两个块是 ["ab", "cde"] ，对应 t[0:2] 和 t[2:5] 。这已经在 dp[2][2]=0 时，加上 "cde" 合并次数 2，得到 2。检查是否更小： dp[3][3] 对应 "abc" 匹配 "abc" 时，最后块 "c" 是单个字符， dp[3][3]=0 ，再加 "de" 合并一次，总共1？不对，那样是 "abc" 与 "de" 合并成 "abcde" 吗？不，我们要整个 s 匹配 t ， "ab" 与 "cde" 之间是独立的块，不需要合并这两个大块。所以最优是 1 次合并（合并 "a" 和 "b" 成 "ab" ， "c" 、 "d" 、 "e" 不合并或合并成 "cde" 需要 2 次合并）。等等，我们要覆盖整个 s 为 t ， t="ab cde" 对应两块， "ab" 需要合并一次（ a , b 合并）， "cde" 需要合并两次（ c , d 合并成 "cd" ，再与 "e" 合并成 "cde" ），总共 3 次？但这是将 s 变成 ["ab", "cde"] 两个块的过程：初始 [a,b,c,d,e] 五个块，要变成 [ab, cde] 两块，需要合并次数是 5-2=3 次。但我们可以让 "cde" 内部不合并吗？不行，因为 "cde" 是一个块，它必须是由三个单字符块合并两次得到。所以总合并次数=3。但前面计算 dp[5][5] 时， k=2 对应 "cde" 合并 2 次，加上 "ab" 合并 1 次（在 dp[2][2] 里？），检查 dp[2][2] 是怎么来的： dp[2][2]=0 表示 "ab" 作为两个单字符块，没合并。但实际最终我们需要 "ab" 是一个块，所以合并 1 次应加在 "ab" 这一段上。所以状态定义需调整： dp[i][j] 表示匹配完后，最后一块是合并好的一个块（即最后一段内部已合并成一个整体），这样转移时，最后一段的合并次数是 len-1 次。之前公式已体现： dp[i][j] = dp[k][j-len] + (len-1) 。这样 dp[2][2] 表示 s[0:2] 匹配 t[0:2] 且最后是一个块，那必须 k=0 时， len=2 ， dp[0][0]+1=1 ，所以 dp[2][2]=1 。则 dp[5][5] 在 k=2 时， len=3 ， dp[2][2]=1 ，加上 3-1=2 ，总 3 次。这是对的。再检查 dp[2][2] 能否是 0？如果是 0 表示 "ab" 是两个块，但最后整体匹配 t 时， t[0:2] 是一个块 "ab" ，所以不允许最后是两个块，因此必须合并成一块。所以在 dp 定义中，最后一块必须是一个整体块。这样结果就是最少合并次数 3。算法步骤总结如果 len(s) < len(t) 或 s 与 t 的字符集合顺序不一致（但需完全匹配），直接返回 -1（实际在 DP 中不可行会 INF）。初始化 dp[n+1][m+1] 为 INF， dp[0][0] = 0 。对于每个 i 从 1 到 n，每个 j 从 1 到 m：枚举最后一块长度 len 从 1 到 min(i, j) ，令 k = i - len （最后一块在 s 中起始下标）。检查 s[k:i] == t[j-len:j] 。如果相等，则 dp[i][j] = min(dp[i][j], dp[k][j-len] + (len-1)) 。如果 dp[n][m] 是 INF，返回 -1，否则返回它。时间复杂度 O(n² m) 可优化到 O(n m) 吗？这里 n 和 m 相等，所以 O(n³)。但实际可优化：因为 len 从 1 到 i，j 需 ≥ len，且子串相等检查可预先哈希加速。举例验证 s = "abc" , t = "abc" ，n=m=3。 i=1,j=1 ： len=1 , s[0:1]="a" , t[0:1]="a" 相等， dp[1][1] = dp[0][0]+0=0 。 i=2,j=2 ： len=1 ： s[1:2]="b" , t[1:2]="b" 相等， dp[2][2]=dp[1][1]+0=0 。 len=2 ： s[0:2]="ab" , t[0:2]="ab" 相等， dp[2][2]=min(0, dp[0][0]+1=1)=0 。 i=3,j=3 ： len=1 ： s[2:3]="c" , t[2:3]="c" 相等， dp[3][3]=dp[2][2]+0=0 。 len=2 ： s[1:3]="bc" , t[1:3]="bc" 相等， dp[3][3]=min(0, dp[1][1]+1=1)=0 。 len=3 ： s[0:3]="abc" , t[0:3]="abc" 相等， dp[3][3]=min(0, dp[0][0]+2=2)=0 。结果 0，正确。边界与不可行情况若 s = "abcde" , t = "abf" ，则 s[2]="c" 对 t[2]="f" 不匹配，所有可能划分都会在某处不相等，最终 dp[n][m] 为 INF，返回 -1。这样，我们就得到了一个完整的区间 DP 解法。