09-02 leetcode-2707

Medium 的 DP 题

题目

You are given a 0-indexed string s and a dictionary of words dictionary. You have to break s into one or more non-overlapping substrings such that each substring is present in dictionary. There may be some extra characters in s which are not present in any of the substrings.

Return the minimum number of extra characters left over if you break up s optimally.

题解

看到最小/最大之类的关键字首先考虑 DP，这题也不例外

假设我们 dp[i] 代表在 i 处的剩下的字符串数量，那么我们递推公式可以这样考虑

当我们不选择 i 的时候，那么第 i + 1 个处的值一定会 +1 那么 dp[i+1] = dp[i] + 1
选的话，那么我们遍历从 0 到 i，如果存在 s[j,i] 在 dictionary 中，那么 dp[i+1] = min(dp[i+1], dp[j])

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

这里存在另外一个可能的优化思路，就是我们可以将 dictionary 转换为一个 Trie 树，这样我们就可以在常数（最长字符串的长度）的时间内判断一个字符串是否在 dictionary 中。

class TreeNode:
    def __init__(self):
        self.children: dict[str, "TreeNode"] = {}

    def get(self, key: str) -> Optional["TreeNode"]:
        return self.children.get(key)


class TrieTree:
    def __init__(self):
        self.root: TreeNode = TreeNode()
        self.ends = {}

    def insert(self, word: str):
        root = self.root
        for item in word:
            root = root.children.setdefault(item, TreeNode())
        self.ends[root] = len(word) + 1

    def search(self, word: str) -> bool:
        root = self.root
        for item in word:
            root = root.children.get(item)
            if not root:
                return False
        return root in self.ends


class Solution:
    def minExtraChar(self, s: str, dictionary: list[str]) -> int:
        tree = TrieTree()
        for word in dictionary:
            tree.insert(word)
        dp = [0] * (len(s) + 1)
        for i in range(len(s)):
            dp[i + 1] = dp[i] + 1
            for j in range(i + 1):
                if tree.search(s[j:i + 1]):
                    dp[i + 1] = min(dp[i + 1], dp[j])
        return dp[-1]

Comments