LeetCode 2707：字符串中的额外字符问题求解求助

问题背景 #

我在解决LeetCode每日一题时遇到瓶颈，题目要求：给定字符串s和单词字典dictionary，将s拆分为一个或多个不重叠子串（每个子串都在字典中），返回最优拆分后剩余的最少额外字符数。

给定输入：

s = "rkmsilizktprllwoimafyuqmeqrujxdzgp"
dictionary = ["afy","lyso","ymdt","uqm","cfybt","lwoim","hdzeg","th","rkmsi","d","e","tp","r","jx","tofxe","etjx","llqs","cpir","p","ncz","ofeyx","eqru","l","demij","tjky","jgodm","y","ernt","jfns","akjtl","wt","tk","zg","lxoi","kt"]

我当前的代码通过了2020/2028个测试用例，但针对上述输入输出为3，而预期是2。代码如下：

class Solution {
    public int minExtraChar(String s, String[] dictionary) {
        List<String> dictionary2 = new ArrayList<>(); 
        for (String str: dictionary){
            if (s.contains(str)){
                dictionary2.add(str);
            }
        }
        List<String> sorted = dictionary2.stream()
            .sorted(Comparator.comparingInt(String::length).reversed())
            .collect(Collectors.toList());
        for (String a: sorted){
            System.out.println(a);
        }
        for (String str: sorted){
            if (s.contains(str)){
                System.out.println("----------------------------");
                System.out.println(s);
                System.out.println(str);
                String ak = " ";
                ak = ak.repeat(str.length());
                s = s.replace(str,ak);
            }
        }
        s = s.replace(" ","");
        System.out.println(s);
        return s.length();
    }
}

问题分析 #

你当前的贪心思路（优先替换最长匹配子串）存在本质缺陷：贪心选择最长子串不一定能得到全局最优解。比如某个长串的替换可能会占用后续更优的短串匹配位置，导致最终剩余字符更多。

以上述输入为例，你的代码优先替换了长串，但可能存在一种拆分方式，通过舍弃某个长串的匹配，让更多短串匹配成功，从而减少剩余字符。这种情况无法通过修改现有贪心逻辑解决，必须换用正确的算法思路。

解决方案：改用动态规划 #

这类求全局最优解的问题，动态规划是标准解法，需要重新编写代码。

动态规划思路 #

1. 定义dp[i]表示字符串s的前i个字符的最少额外字符数。
2. 初始状态：dp[0] = 0（空字符串无额外字符），dp[i]默认初始化为dp[i-1]+1（假设第i个字符是额外字符）。
3. 状态转移：对于每个位置i，遍历所有可能的起始位置j（0<=j<i），如果子串s[j:i]存在于字典中，则dp[i] = min(dp[i], dp[j])。
4. 最终结果：dp[s.length()]。

优化点 #

• 将字典存入HashSet，将子串查询复杂度降至O(1)。
• 记录字典中单词的最大长度，限制j的遍历范围，减少不必要的子串截取操作。

修正后的代码 #

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int minExtraChar(String s, String[] dictionary) {
        Set<String> dictSet = new HashSet<>();
        int maxWordLen = 0;
        // 初始化字典集合，同时记录最长单词长度
        for (String word : dictionary) {
            dictSet.add(word);
            maxWordLen = Math.max(maxWordLen, word.length());
        }
        
        int strLen = s.length();
        int[] dp = new int[strLen + 1];
        
        // 初始化dp数组
        for (int i = 1; i <= strLen; i++) {
            // 默认当前字符为额外字符，继承前一个位置的最优解+1
            dp[i] = dp[i - 1] + 1;
            // 只遍历可能匹配字典单词的区间
            int start = Math.max(0, i - maxWordLen);
            for (int j = start; j < i; j++) {
                String subStr = s.substring(j, i);
                if (dictSet.contains(subStr)) {
                    dp[i] = Math.min(dp[i], dp[j]);
                }
            }
        }
        return dp[strLen];
    }
}

代码解释 #

• 字典转HashSet：大幅提升子串存在性的查询效率，避免遍历列表的O(n)开销。
• dp数组初始化：每个位置先默认当前字符无法匹配，以此为基础再尝试寻找更优解。
• 状态转移逻辑：遍历所有可能的子串结尾位置，若子串在字典中，则更新当前位置的最优解。
• maxWordLen优化：只检查长度不超过字典最长单词的子串，减少无效的循环次数，提升运行效率。

内容的提问来源于stack exchange，提问作者Homie_Tomie