字符串中的额外字符

标签: 字典树 数组 哈希表 字符串 动态规划

难度: Medium

给你一个下标从 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 中的单词互不相同。

Submission

运行时间: 52 ms

内存: 16.6 MB

class Solution:
    def minExtraChar(self, s: str, dictionary: List[str]) -> int:
        # nxt = [[0 for _ in range(26)]]
        # cnt = 0
        # exist = [False]
        # for word in dictionary :
        #     p = 0
        #     for ch in word[::-1] :
        #         c = ord(ch) - ord('a')
        #         if not nxt[p][c] :
        #             cnt += 1
        #             nxt[p][c] = cnt
        #             nxt.append([0 for _ in range(26)])
        #             exist.append(False)
        #         p = nxt[p][c]
        #     exist[p] = True
        # n = len(s)
        # dp = [0 for _ in range(n + 1)]
        # for i in range(n) :
        #     dp[i + 1] = dp[i] + 1
        #     p = 0
        #     for j in range(i, -1, -1) :
        #         c = ord(s[j]) - ord('a')
        #         if p < 0 or not nxt[p][c] :
        #             p = -1
        #             break
        #         else :
        #             p = nxt[p][c]
        #             if exist[p] and dp[i + 1] > dp[j] :
        #                 dp[i + 1] = dp[j]
        # return dp[-1]


        dic = dict()
        for word in dictionary :
            if word[-1] not in dic :
                dic[word[-1]] = [word]
            else :
                dic[word[-1]].append(word)
        n = len(s)
        dp = [0]
        for i in range(n) :
            dp.append(dp[-1] + 1)
            if s[i] in dic :
                for j in dic[s[i]] :
                    k = i + 1 - len(j)
                    if s[k: i + 1] == j :
                        if dp[-1] > dp[k] :
                            dp[-1] = dp[k]
        return dp[-1]

Explain

题解采用动态规划的方法来解决字符串分割问题。首先，创建一个字典 dic，将每个单词按其最后一个字符分类存储。使用动态规划数组 dp，其中 dp[i] 表示字符串 s 的前 i 个字符中未被使用的最小字符数量。遍历字符串 s 的每个字符，并检查是否有字典中的单词以该字符结束，如果是，则尝试匹配整个单词。如果匹配成功，更新 dp 数组以尝试减少未使用的字符数量。最终，dp 数组的最后一个元素 dp[n]（其中 n 是字符串 s 的长度）给出了分割后剩余的最少字符数。

时间复杂度: O(n * m)

空间复杂度: O(n)

class Solution:
    def minExtraChar(self, s: str, dictionary: List[str]) -> int:
        # 构建字典，将单词按照最后一个字符进行分类
        dic = dict()
        for word in dictionary :
            if word[-1] not in dic :
                dic[word[-1]] = [word]
            else :
                dic[word[-1]].append(word)
        n = len(s)
        # 初始化动态规划数组
        dp = [0]
        for i in range(n) :
            # 默认剩余字符加1（当前字符未使用的情况）
            dp.append(dp[-1] + 1)
            # 检查当前字符是否可以是某个单词的结尾字符
            if s[i] in dic :
                for j in dic[s[i]] :
                    # 计算匹配单词的起始位置
                    k = i + 1 - len(j)
                    # 检查是否完全匹配
                    if s[k: i + 1] == j :
                        # 更新 dp 数组，尝试减少未使用的字符数
                        if dp[-1] > dp[k] :
                            dp[-1] = dp[k]
        # 返回分割后剩余的最少字符数
        return dp[-1]

Explore

在此题解中，字典的使用主要是为了快速定位和匹配以特定字符结束的单词。当处理字符串s中的每一个字符时，可以直接通过这个字符找到所有可能以此字符为结尾的单词，然后尝试匹配。这种方法减少了不必要的比对，提高了效率，使得只有在有潜在匹配可能时才进行字符串的比对，从而优化了算法的执行时间。

动态规划数组dp的每个位置i代表的是从字符串s的开头到第i个字符最少的未使用字符数量。更新dp[i]时，首先将dp[i-1]的值加1，假设第i个字符未被任何单词使用。随后检查是否有以s[i]结尾的单词，如果找到，则尝试从i减去该单词长度的位置开始匹配整个单词。如果匹配成功，比较dp[i]（考虑当前字符未使用的情况）和dp[k]（匹配单词后的位置）的值，取较小的那个，以确保dp[i]表示的是最小的未使用字符数量。

题解中仅在单词完全匹配时更新dp数组，因为只有完全匹配的单词才能确认从匹配点到当前字符间没有未使用的字符。如果单词只是部分匹配，那么这部分匹配不能帮助减少未使用的字符数量，因此没有必要记录部分匹配的状态。记录部分匹配可能引入复杂度并且不会对解题产生帮助，因为它不改变任何dp数组的值。

这种条件判断的逻辑依据是寻找使得未使用字符数量最小化的可能。dp[k]表示在匹配到当前检查的单词之前的最小未使用字符数量。如果dp[k]的值加上从k到当前字符的匹配（假设是0，因为假定单词完全匹配了）小于仅将当前字符视为未使用的情况（dp[-1]），那么更新dp[-1]为dp[k]会使得未使用字符数量达到当前可知的最小值。这保证了dp数组确实表示每个位置可能的最小未使用字符数。