Medium

题目描述

给你一个下标从 0 开始的字符串 s 和一个单词字典 dictionary。你需要将 s 分解为一个或多个互不重叠的子字符串，使得每个子字符串都在 dictionary 中出现。s 中可能会有一些额外的字符不属于任何子字符串。

返回在最优分解方案下剩余的最少额外字符数。

示例 1：

输入：s = "leetscode", dictionary = ["leet","code","leetcode"]
输出：1
解释：我们可以将 s 分解为两个子字符串："leet" (下标 0 到 3) 和 "code" (下标 5 到 8)。只有 1 个未使用的字符 (下标 4)，所以返回 1。

示例 2：

输入：s = "sayhelloworld", dictionary = ["hello","world"]
输出：3
解释：我们可以将 s 分解为两个子字符串："hello" (下标 3 到 7) 和 "world" (下标 8 到 12)。下标 0、1、2 的字符没有在任何子字符串中使用，因此被认为是额外字符。返回 3。

提示：

  • 1 <= s.length <= 50
  • 1 <= dictionary.length <= 50
  • 1 <= dictionary[i].length <= 50
  • dictionary[i] 和 s 仅由小写英文字母组成
  • dictionary 包含不同的单词

解题思路

这道题可以用动态规划来解决。核心思路是定义 dp[i] 表示字符串 s[0:i] 的最优分解方案下的最少额外字符数。

状态转移： 对于位置 i，我们有两种选择：

  1. 将 s[i-1] 作为额外字符：dp[i] = dp[i-1] + 1
  2. 如果存在某个字典中的单词 word 使得 s[i-len(word):i] == word，那么：dp[i] = min(dp[i], dp[i-len(word)])

优化技巧： 为了快速查找字典中的单词，可以使用哈希集合存储所有单词。对于每个位置 i，我们向前检查所有可能的子字符串，看是否在字典中存在。

初始状态： dp[0] = 0，表示空字符串没有额外字符。

最终答案： dp[n]，其中 n 是字符串 s 的长度。

时间复杂度方面，由于字符串长度和字典单词长度都不超过 50，所以这个解法在给定约束下是高效的。

代码实现

class Solution {
public:
    int minExtraChar(string s, vector<string>& dictionary) {
        int n = s.length();
        unordered_set<string> dict(dictionary.begin(), dictionary.end());
        vector<int> dp(n + 1, 0);
        
        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i - 1] + 1; // 当前字符作为额外字符
            
            for (int j = 0; j < i; j++) {
                string sub = s.substr(j, i - j);
                if (dict.count(sub)) {
                    dp[i] = min(dp[i], dp[j]);
                }
            }
        }
        
        return dp[n];
    }
};

class Solution:
    def minExtraChar(self, s: str, dictionary: List[str]) -> int:
        n = len(s)
        dict_set = set(dictionary)
        dp = [0] * (n + 1)
        
        for i in range(1, n + 1):
            dp[i] = dp[i - 1] + 1  # 当前字符作为额外字符
            
            for j in range(i):
                sub = s[j:i]
                if sub in dict_set:
                    dp[i] = min(dp[i], dp[j])
        
        return dp[n]

public class Solution {
    public int MinExtraChar(string s, string[] dictionary) {
        int n = s.Length;
        HashSet<string> dictSet = new HashSet<string>(dictionary);
        int[] dp = new int[n + 1];
        
        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i - 1] + 1; // 当前字符作为额外字符
            
            for (int j = 0; j < i; j++) {
                string sub = s.Substring(j, i - j);
                if (dictSet.Contains(sub)) {
                    dp[i] = Math.Min(dp[i], dp[j]);
                }
            }
        }
        
        return dp[n];
    }
}

var minExtraChar = function(s, dictionary) {
    const n = s.length;
    const dictSet = new Set(dictionary);
    const dp = new Array(n + 1).fill(0);
    
    for (let i = 1; i <= n; i++) {
        dp[i] = dp[i - 1] + 1; // 当前字符作为额外字符
        
        for (let j = 0; j < i; j++) {
            const sub = s.substring(j, i);
            if (dictSet.has(sub)) {
                dp[i] = Math.min(dp[i], dp[j]);
            }
        }
    }
    
    return dp[n];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n³)
空间复杂度O(n + m)

其中 n 是字符串 s 的长度，m 是字典中所有单词的总长度。时间复杂度中的 n³ 来自于双重循环遍历所有可能的子字符串位置，空间复杂度包括 dp 数组的 O(n) 和哈希集合存储字典的 O(m)。

相关题目