2707：字符串中的额外字符（1735 分）

2023-05-27 约 492 字预计阅读 1 分钟次阅读

力扣第 105 场双周赛第 2 题

题目

给你一个下标从 0 开始的字符串 s 和一个单词字典 dictionary 。你需要将 s 分割成若干个 互不重叠 的子字符串，每个子字符串都在 dictionary 中出现过。s 中可能会有一些 额外的字符 不在任何子字符串中。

请你采取最优策略分割 s ，使剩下的字符最少。

示例 1：

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

示例 2：

输入：s = "sayhelloworld", dictionary = ["hello","world"]
输出：3
解释：将 s 分成两个子字符串：下标从 3 到 7 的 "hello" 和下标从 8 到 12 的 "world" 。下标为 0 ，1 和 2 的字符没有使用，所以我们返回 3 。

提示：

1 <= s.length <= 50
1 <= dictionary.length <= 50
1 <= dictionary[i].length <= 50
dictionary[i] 和 s 只包含小写英文字母。
dictionary 中的单词互不相同。

相似问题：

0139：单词拆分

分析

#1

按选不选最后一个字符，递推即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


class Solution:
    def minExtraChar(self, s: str, dictionary: List[str]) -> int:
        vis = set(dictionary)
        n = len(s)
        f = [0]*(n+1)
        for i in range(1,n+1):
            f[i]=1+f[i-1]
            for j in range(i):
                if s[j:i] in vis:
                    f[i]=min(f[i],f[j])
        return f[-1]

130 ms

#2

可以用字典树优化查询过程。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class Solution:
    def minExtraChar(self, s: str, dictionary: List[str]) -> int:
        T = lambda: defaultdict(T)
        trie = T()
        for w in dictionary:
            p = trie
            for c in w[::-1]:
                p = p[c]
            p['#'] = ''
        n = len(s)
        f = [0]*(n+1)
        for i in range(1,n+1):
            f[i]=1+f[i-1]
            p = trie
            for j in range(i-1,-1,-1):
                if s[j] not in p:
                    break
                p = p[s[j]]
                if '#' in p:
                    f[i]=min(f[i],f[j])
        return f[-1]

106 ms

目录

2707：字符串中的额外字符（1735 分）

题目

分析

#1

#2

解答