Kimi LeetCode 2911. 得到 K 个半回文串的最少修改次数 Java实现
这是 LeetCode 2911「得到 K 个半回文串的最少修改次数」的 Java 实现。
核心思路
这道题分为两个部分：
- 预处理
cost[i][j]：计算将子串s[i..j]变成半回文串的最小修改次数 - 动态规划：将字符串分成 k 段，使总修改次数最少
半回文串的定义
一个长度为len的字符串是半回文串，当且仅当存在1 <= d < len且len % d == 0，使得将字符串按模d分成d个组后，每个组都是回文串。
例如"adbgad"，d=2时分成两组："abg"（下标 0,2,4）和"dad"（下标 1,3,5），两组都是回文串。
优化点
- 预处理每个长度的所有因子，避免重复计算
getCostD方法按偏移量offset（0 到 d-1）分别检查每组回文需要的修改次数
Java 代码
classSolution{publicintminimumChanges(Strings,intk){finalintn=s.length();// factors[i] := i 的所有真因子 (1 <= d < i 且 i % d == 0)List<Integer>[]factors=getFactors(n);// cost[i][j] := 将 s[i..j] 变成半回文串的最小修改次数int[][]cost=getCost(s,n,factors);// dp[i][j] := 将 s[i:] 分成 j 个半回文子串的最小修改次数// 这里采用从右往左的 DP，也可以改成从左往右int[][]dp=newint[n+1][k+1];for(int[]row:dp){Arrays.fill(row,n);// 用 n 作为无穷大（最大修改次数不会超过 n）}dp[n][0]=0;// 空串分成 0 段，修改次数为 0for(inti=n-1;i>=0;--i){for(intj=1;j<=k;++j){// 枚举下一段的结束位置 lfor(intl=i+1;l<n;++l){dp[i][j]=Math.min(dp[i][j],dp[l+1][j-1]+cost[i][l]);}}}returndp[0][k];}// 预处理 1~n 每个数的真因子privateList<Integer>[]getFactors(intn){List<Integer>[]factors=newList[n+1];for(inti=1;i<=n;++i){factors[i]=newArrayList<>();factors[i].add(1);// 1 是所有数的因子}for(intd=2;d<n;++d){for(inti=d*2;i<=n;i+=d){factors[i].add(d);}}returnfactors;}// 计算所有子串变成半回文串的最小代价privateint[][]getCost(finalStrings,intn,List<Integer>[]factors){int[][]cost=newint[n][n];for(inti=0;i<n;++i){for(intj=i+1;j<n;++j){// 长度至少为 2 才能是半回文finalintlength=j-i+1;intminCost=length;// 最大不会超过长度for(finalintd:factors[length]){minCost=Math.min(minCost,getCostD(s,i,j,d));}cost[i][j]=minCost;}}returncost;}// 计算将 s[i..j] 按周期 d 变成半回文串的修改次数// 按模 d 的余数分成 d 个组，每组需要是回文串privateintgetCostD(finalStrings,inti,intj,intd){intcost=0;// 对每个偏移量 offset (0 到 d-1)，检查对应的组for(intoffset=0;offset<d;++offset){intl=i+offset;// 组的左端点intr=j-d+1+offset;// 组的右端点// 在该组内，以 d 为步长向中间靠拢，检查回文while(l<r){if(s.charAt(l)!=s.charAt(r)){++cost;}l+=d;r-=d;}}returncost;}}复杂度分析
项目 复杂度
时间O(n³)— 预处理O(n³)（枚举子串O(n²)× 枚举因子和检查O(n)），DP 部分O(n²k)
空间O(n²)—cost数组O(n²)，dp数组O(nk)，因子数组O(n log n)
由于题目限制n <= 200，O(n³)的算法完全可以通过。