2707.字符串中的额外字符

链接：2707.字符串中的额外字符
难度：Medium
标签：字典树、数组、哈希表、字符串、动态规划
简介：给你一个下标从 0 开始的字符串 s 和一个单词字典 dictionary 。你需要将 s 分割成若干个 互不重叠 的子字符串，每个子字符串都在 dictionary 中出现过。s 中可能会有一些 额外的字符 不在任何子字符串中。请你采取最优策略分割 s ，使剩下的字符 最少 。

题解 1 - python

• 编辑时间：2024-01-09
• 执行用时：156ms
• 内存消耗：16.97MB
• 编程语言：python
• 解法介绍：dp[i]表示以i为结尾的字符串省略的最多字符。

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