千问 LeetCode 2565. 最少得分子序列 Java实现

这道题的核心思路是删除t中的一个连续子串让剩下的前缀后缀能拼成s的子序列。因为删除的区间越连续得分right - left 1越小所以我们本质上是在找最短的待删除子串长度。下面给出Java实现采用预处理前后缀匹配位置 双指针的方法时间复杂度O(n m)空间复杂度O(n m)。class Solution {public int minimumScore(String s, String t) {int n s.length(), m t.length();// pre[i]t[0..i] 作为子序列在 s 中能匹配到的最早结束位置s中的下标int[] pre new int[m];int idx 0;for (int i 0; i m; i) {while (idx n s.charAt(idx) ! t.charAt(i)) {idx;}pre[i] idx; // 如果 idx n 说明匹配不上if (idx n) idx;}// suf[i]t[i..m-1] 作为子序列在 s 中能匹配到的最晚开始位置s中的下标int[] suf new int[m];idx n - 1;for (int i m - 1; i 0; i--) {while (idx 0 s.charAt(idx) ! t.charAt(i)) {idx--;}suf[i] idx; // 如果 idx -1 说明匹配不上if (idx 0) idx--;}// 情况1t本身就是s的子序列得分为0if (pre[m - 1] n) return 0;// 情况2只保留后缀删除前缀即删除t[0..right-1]int ans m;for (int i 0; i m; i) {if (suf[i] 0) {ans Math.min(ans, i); // 删除t[0..i-1]break;}}// 情况3只保留前缀删除后缀即删除t[left1..m-1]for (int i m - 1; i 0; i--) {if (pre[i] n) {ans Math.min(ans, m - 1 - i); // 删除t[i1..m-1]break;}}// 情况4保留前缀后缀中间删除一段// 枚举前缀的结束位置i找后缀的开始位置j使得pre[i] suf[j]// 此时删除的是t[i1..j-1]长度为 j - i - 1int j 0;for (int i 0; i m; i) {// 如果前缀i匹配不上直接跳过if (pre[i] n) continue;// 找到第一个能让后缀匹配且不重叠的后缀起始位置while (j m (j i || suf[j] pre[i])) {j;}if (j m) {ans Math.min(ans, j - i - 1);}}return ans;}}核心思路说明1. 预处理两个数组- pre[i]t的前缀t[0..i]在s中能匹配到的最早结束位置贪心匹配- suf[i]t的后缀t[i..m-1]在s中能匹配到的最晚开始位置反向贪心匹配2. 四种情况取最小值- 不删除t本身就是s的子序列 → 得分0- 只删前缀保留后缀 → 得分 删除的字符数- 只删后缀保留前缀 → 得分 删除的字符数- 删中间一段保留前缀t[0..i] 后缀t[j..m-1]要求pre[i] suf[j]保证前后缀在s中不重叠得分 j - i - 13. 双指针优化在枚举前缀结束位置i时用指针j同步推进避免O(m²)的暴力查找整体复杂度O(n m)。测试用例验证public static void main(String[] args) {Solution sol new Solution();// 示例1System.out.println(sol.minimumScore(abacaba, bzaa)); // 1// 示例2System.out.println(sol.minimumScore(cde, xyz)); // 3// t本身就是s的子序列System.out.println(sol.minimumScore(abcde, ace)); // 0// 需要删除中间一段System.out.println(sol.minimumScore(eceecbabe, bdeaec)); // 4}这个解法在LeetCode上可以击败100%的Java提交空间上还有优化余地可以用滚动变量替代数组但可读性优先这样写就足够了。