2707-字符串中的额外字符
给你一个下标从 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
中的单词互不相同。
前置知识:动态规划入门
详见 动态规划入门:从记忆化搜索到递推【基础算法精讲 17】 。
APP 用户需要分享到微信打开视频链接。
一、寻找子问题
为了方便转成递推,从后往前考虑。
设 n 为 s 的长度。我们可以:
- 直接跳过 s 的最后一个字符,那么问题变成 s 的前 n-1 个字符的子问题。
- 考虑「枚举选哪个」,如果从 s[j] 开始的后缀在 dictionary 中,那么问题变成 s 的前 j-1 个字符的子问题。
二、记忆化搜索
根据上面的讨论,定义 dfs}(i) 表示 s 的前 i 个字符的子问题。
- 跳过 s 的最后一个字符,有 dfs}(i)=\textit{dfs}(i-1)+1。
- 考虑「枚举选哪个」,如果从 s[j] 到 s[i] 的子串在 dictionary 中,有
\textit{dfs}(i)=\min_{j=0}^{i}\textit{dfs}(j-1)
这两种情况取最小值。
递归边界:dfs}(-1)=0。
答案:dfs}(n-1)。
1 | class Solution: |
1 | func minExtraChar(s string, dictionary []string) int { |
复杂度分析
- 时间复杂度:\mathcal{O}(L + n^3),其中 n 为 s 的长度,L 为 dictionary 所有字符串的长度之和。预处理哈希表需要 \mathcal{O}(L) 的时间。动态规划的时间复杂度 = 状态个数 \times 单个状态的计算时间。本题中状态个数等于 \mathcal{O}(n),单个状态的计算时间为 \mathcal{O}(n^2),因此时间复杂度为 \mathcal{O}(n^3)。所以总的时间复杂度为 \mathcal{O}(L + n^3)。
- 空间复杂度:\mathcal{O}(n+L)。
三、1:1 翻译成递推
我们可以去掉递归中的「递」,只保留「归」的部分,即自底向上计算。
做法:
- dfs 改成 f 数组;
- 递归改成循环(每个参数都对应一层循环);
- 递归边界改成 f 数组的初始值。
具体来说,f[i] 的含义和 dfs}(i) 的含义是一样的,都表示 s 的前 i 个字符的子问题。
相应的递推式(状态转移方程)也和 dfs 的一致:
- 跳过 s 的最后一个字符,有 f[i]=f[i-1]+1。
- 考虑「枚举选哪个」,如果从 s[j] 到 s[i] 的子串在 dictionary 中,有
f[i]=\min_{j=0}^{i}f[j-1]
这两种情况取最小值。
但当 i=0 或 j=0 时,等号右边会出现负数下标。或者说,这种定义方式没有状态能表示递归边界,即出界的情况。
解决办法:在 f 数组左边添加一个状态来表示 i=-1,把原来的 f[i] 改成 f[i+1],f[j-1] 改成 f[j]。
相应的递推式为 f[i+1]=f[i]+1 以及 f[i+1]=\min\limits_{j=0}^{i}f[j]。
初始值 f[i]=0。(翻译自 dfs}(-1)=0。)
答案为 f[n]。(翻译自 dfs}(n-1)。)
1 | class Solution: |
1 | class Solution { |
1 | class Solution { |
1 | func minExtraChar(s string, dictionary []string) int { |
复杂度分析
- 时间复杂度:\mathcal{O}(L + n^3),其中 n 为 s 的长度,L 为 dictionary 所有字符串的长度之和。预处理哈希表需要 \mathcal{O}(L) 的时间。动态规划的时间复杂度 = 状态个数 \times 单个状态的计算时间。本题中状态个数等于 \mathcal{O}(n),单个状态的计算时间为 \mathcal{O}(n^2),因此时间复杂度为 \mathcal{O}(n^3)。所以总的时间复杂度为 \mathcal{O}(L + n^3)。
- 空间复杂度:\mathcal{O}(n+L)。
Comments