2026-10-18转换字符串的最小成本Ⅲ。用go语言给定两个字符串 source 和 target以及若干条替换规则。每条规则包含一个模式串、一个替换串和一个基础代价模式串与替换串长度相同代价数组中对应给出该规则的基础代价。可以按任意顺序、任意次数使用这些规则。每次使用时在当前字符串中选一段连续区间区间长度必须等于所选规则的模式串长度并且这段区间里的每个位置此前都没有被任何已执行的操作覆盖过。随后逐位检查当前字符必须与模式串对应字符相同或者模式串该位是星号通配符。满足后把整段字符替换成该规则的替换串替换串按原样使用不含通配符。一次操作的总代价等于该规则的基础代价加上模式串中星号的数量。某个位置只要在某次操作中被覆盖之后就不能再参与任何操作。由于模式和替换串等长每次操作后字符串长度不变字符位置也保持不变。目标是求把 source 变成 target 所需的最小总代价。如果无论怎样安排都无法完成转换则返回负一。1 source.length, target.length 5000。source 和 target 仅由小写英文字母组成。1 rules.length costs.length 200。rules[i] [patterni, replacementi]。1 patterni.length replacementi.length 20。patterni 至少包含一个小写英文字母且最多包含 5 个 ‘*’ 字符。replacementi 仅包含小写英文字母。1 costs[i] 1000。输入 source “hello”, target “world”, rules [[“he”,“wo”],[“llo”,“rld”]], costs [3,4]。输出 7。解释应用 rules[0]将 “he” 替换为 “wo”成本为 3字符串变为 “wollo”。应用 rules[1]将 “llo” 替换为 “rld”成本为 4字符串变为 “world”。总成本为 3 4 7。题目来自力扣3995。大体步骤如下一、预处理每条规则的成本代码一开始遍历所有规则。对于第 k 条规则它的基础成本是 costs[k]。由于每次应用规则时实际成本还要加上模式串 pattern 中星号 ‘*’ 的个数所以代码直接把这个星号数量累加到 costs[k] 上。这样处理后后面动态规划里一旦决定使用第 k 条规则只需要加上 costs[k] 即可不需要每次重新统计星号数量。这一步不改变规则内容只改变成本数组的数值。因为 costs 是切片代码是在原切片上累加。二、定义模式匹配判断代码定义了一个内部匹配函数 isMatch用来判断某个模式串 pattern 是否能匹配从某个起始位置开始的字符串片段。判断规则是逐位比较 pattern 和当前字符串片段。如果 pattern 当前位不是星号那么它必须与字符串片段的对应字符完全相同如果 pattern 当前位是星号则它可以匹配任意字符直接通过。需要注意代码在转移时传给匹配函数的是原始 source 从位置 i 开始的片段。原因是动态规划按从左到右处理位置 i 及其右边尚未被任何规则覆盖所以这些位置上的字符仍然是 source 的原始字符。只有已经被处理过的前缀才不再参与后续操作。三、定义动态规划状态设 n 为 source 的长度。代码定义数组 f长度为 n1。f[i] 表示把 source 的前 i 个字符处理成 target 的前 i 个字符并且前 i 个位置以后不再参与任何操作时所需要的最小总成本。换句话说f[i] 表示当前已经处理到下标 i接下来从下标 i 开始考虑。f[n] 就是整个字符串处理完成后的最小成本。初始化时f[0] 等于 0表示还没有处理任何字符时成本为 0。f[1] 到 f[n] 初始化为一个非常大的值表示暂时不可达。代码隐含以 source 的长度作为 DP 长度因此默认 source 和 target 等长。按题意如果长度不同显然无法通过这种等长替换完成转换应当返回 -1这段代码没有显式写长度判断。四、外层按位置从左到右推进外层循环让 i 从 0 到 n-1 依次遍历。对于每个位置 i先检查 f[i] 是否仍然是最大值。如果是说明前 i 个字符无法以任何方式处理完成当前位置不可能作为后续操作的起点于是直接跳过。如果 f[i] 可达就从位置 i 出发考虑两种选择保留位置 i 的字符不覆盖或者从位置 i 开始应用某条规则覆盖一段连续区间。五、选择不覆盖当前位置 i如果 source[i] 和 target[i] 相同那么位置 i 可以保持不变。此时前 i 个字符已经处理完成并且位置 i 也不需要被覆盖所以可以推进到 i1。新的成本仍然是 f[i]。代码执行的是松弛操作如果 f[i] 比当前记录的 f[i1] 更小就把 f[i1] 更新为 f[i]。如果 source[i] 和 target[i] 不同那么不覆盖位置 i 就无法让它变成目标字符因此不能通过“保留”这种方式推进。六、选择用某条规则覆盖从 i 开始的一段接下来代码遍历每一条规则 rule[k]。设这条规则的替换串为 replacement模式串为 pattern。因为题目保证 pattern 和 replacement 长度相同所以 replacement 的长度就是这次覆盖区间的长度。设这个长度为 len则这次覆盖的区间是 [i, ilen)。右端点为 r i len。只有满足下面几个条件才可能用这条规则从 i 开始覆盖第一r 不能超过 n也就是覆盖区间必须完全落在当前字符串范围内。第二使用这条规则后的新成本 f[i] costs[k] 必须比当前记录的 f[r] 更小。如果不更小就没有更新必要代码会跳过后续判断。这个条件也起到提前剪枝的作用。第三替换串 replacement 必须完全等于 target 从 i 到 r 的子串。原因是这一段一旦被覆盖其中的位置以后就不能再被任何规则使用因此这段字符的最终结果只能由这次替换决定。如果 replacement 不等于目标子串那么即使这次替换成功这段最终也无法变成 target方案不可行。第四模式串 pattern 必须能够匹配 source 从 i 开始的长度为 len 的片段。这里使用的是原始 source 的对应片段因为位置 i 到 r-1 之前还没有被覆盖仍然保持 source 原始字符。匹配时pattern 中非星号位必须与 source 对应字符相同星号位可以匹配任意字符。以上条件全部满足时说明可以从 i 开始用这条规则覆盖到 r并且这段覆盖后直接变成 target 的对应部分。于是把 f[r] 更新为 f[i] costs[k]表示处理完前 r 个字符的最小成本。七、为什么这样按左端点推进是正确的一次规则应用会覆盖一段连续区间且被覆盖过的位置以后不能再使用。因此任意一个合法方案中所有被覆盖的区间两两不重叠。把这些覆盖区间按左端点从左到右排序就可以看成从字符串最左边开始每个位置要么保持原字符不覆盖要么作为某次规则覆盖的起点覆盖一段长度等于替换串长度的区间然后跳到这段区间的右端点继续处理。未覆盖的位置必须满足 source 与 target 在该位置相同否则最终无法变成 target。被覆盖的区间由于以后不能再改替换串必须直接等于 target 对应区间。模式匹配检查的是原始 source因为该区间在覆盖前还没有被使用过。因此动态规划按 i 从左到右推进枚举“保留一个字符”或“用某条规则覆盖一段”不会漏掉合法方案也能保证区间不重叠。八、用示例走一遍source “hello”target “world”规则为 [“he”,“wo”] 成本 3[“llo”,“rld”] 成本 4。两个模式串都没有星号所以预处理后成本仍是 3 和 4。初始 f[0] 0其余为无穷大。处理 i 0 时source[0] 是 ‘h’target[0] 是 ‘w’不相等所以不能通过保留推进。尝试规则 0replacement 是 “wo”长度 2r 2。target[0:2] 是 “wo”与 replacement 相等pattern “he” 与 source[0:2] “he” 匹配。于是 f[2] 更新为 3。尝试规则 1replacement 是 “llo”长度 3r 3。target[0:3] 是 “wor”不等于 “llo”不能使用。处理 i 1 时f[1] 不可达跳过。处理 i 2 时f[2] 3。source[2] 是 ‘l’target[2] 是 ‘r’不相等不能保留。尝试规则 0replacement “wo” 与 target[2:4] “rl” 不等不能使用。尝试规则 1replacement “rld”长度 3r 5。target[2:5] 是 “rld”与 replacement 相等pattern “llo” 与 source[2:5] “llo” 匹配。于是 f[5] 更新为 f[2] 4 7。最后 f[5] 为 7返回 7。九、返回结果循环结束后如果 f[n] 仍然是最大值说明无法把整个 source 转换成 target返回 -1。如果 f[n] 小于最大值说明存在可行方案返回 f[n]即最小总成本。十、复杂度分析设 n 为 source 的长度m 为规则条数L 为规则中模式串或替换串的最大长度。题目中 L 不超过 20。时间复杂度预处理阶段需要遍历每条规则并统计星号数量耗时 O(mL)。动态规划外层遍历 n 个位置内层遍历 m 条规则对每条规则需要比较替换串与 target 子串长度最多 L还需要用模式串匹配 source 片段长度也最多 L。因此动态规划部分为 O(nmL)。由于 n 至少为 1总时间复杂度为 O(nmL)。额外空间复杂度主要额外空间是动态规划数组 f长度为 n1所以是 O(n)。字符串切片 target[i:r] 和 source[i:] 在 Go 中只是视图不会复制出长度为 L 的新字符串匹配和比较是逐字符进行。成本数组是在原数组上累加不额外分配大数组。因此不计输入字符串和规则本身时总额外空间复杂度为 O(n)。Go完整代码如下packagemainimport(fmtmathstrings)funcminCost(source,targetstring,rules[][]string,costs[]int)int{// 把成本加上 * 的个数这样在 DP 中无需反复统计 * 的个数fori,rule:rangerules{costs[i]strings.Count(rule[0],*)}isMatch:func(pattern,sstring)bool{forj,ch:rangepattern{ifch!*byte(ch)!s[j]{returnfalse}}returntrue}n:len(source)f:make([]int,n1)fori:1;in;i{f[i]math.MaxInt}fori:rangen{iff[i]math.MaxInt{continue}// 不替换下标 iifsource[i]target[i]{f[i1]min(f[i1],f[i])}// 替换子串 [i, ilen(replacement)-1]fork,rule:rangerules{replacement:rule[1]r:ilen(replacement)ifrnf[i]costs[k]f[r]replacementtarget[i:r]isMatch(rule[0],source[i:]){f[r]f[i]costs[k]}}}iff[n]math.MaxInt{returnf[n]}return-1}funcmain(){source:hellotarget:worldrules:[][]string{{he,wo},{llo,rld}}costs:[]int{3,4}result:minCost(source,target,rules,costs)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-defminCost(source,target,rules,costs):# 复制成本数组避免修改原数组costscosts[:]# 将规则中 * 的数量加入对应成本fori,ruleinenumerate(rules):costs[i]rule[0].count(*)defis_match(pattern,s,start):forj,chinenumerate(pattern):ifch!*andch!s[startj]:returnFalsereturnTruenlen(source)INFfloat(inf)f[INF]*(n1)f[0]0foriinrange(n):iff[i]INF:continue# 不替换下标 iifsource[i]target[i]:iff[i]f[i1]:f[i1]f[i]# 尝试用某条规则替换从 i 开始的子串fork,ruleinenumerate(rules):replacementrule[1]rilen(replacement)if(rnandf[i]costs[k]f[r]andreplacementtarget[i:r]andis_match(rule[0],source,i)):f[r]f[i]costs[k]returnf[n]iff[n]INFelse-1if__name____main__:sourcehellotargetworldrules[[he,wo],[llo,rld]]costs[3,4]resultminCost(source,target,rules,costs)print(result)C完整代码如下#includeiostream#includevector#includestring#includeclimits#includealgorithmusingnamespacestd;intminCost(conststringsource,conststringtarget,vectorvectorstringrules,vectorintcosts){// 把 * 的个数累加到成本上for(size_t i0;irules.size();i){costs[i]count(rules[i][0].begin(),rules[i][0].end(),*);}autoisMatch[](conststringpattern,conststrings,intstart)-bool{for(size_t j0;jpattern.size();j){if(pattern[j]!*pattern[j]!s[startj]){returnfalse;}}returntrue;};intn(int)source.size();constintINFINT_MAX;vectorintf(n1,INF);f[0]0;for(inti0;in;i){if(f[i]INF)continue;// 不替换下标 iif(source[i]target[i]){f[i1]min(f[i1],f[i]);}// 尝试用某条规则替换从 i 开始的子串for(size_t k0;krules.size();k){conststringreplacementrules[k][1];intlen(int)replacement.size();intrilen;if(rnf[i]costs[k]f[r]target.compare(i,len,replacement)0isMatch(rules[k][0],source,i)){f[r]f[i]costs[k];}}}returnf[n]INF?f[n]:-1;}intmain(){string sourcehello;string targetworld;vectorvectorstringrules{{he,wo},{llo,rld}};vectorintcosts{3,4};coutminCost(source,target,rules,costs)endl;return0;}