文章目录
题目描述解题思路简单举例哈希集合进行查找动态规划三部曲
代码pythonjavacpp时空复杂度
华为OD算法/大厂面试高频题算法练习冲刺训练
题目描述
给你一个下标从 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 <= 501 <= dictionary.length <= 501 <= dictionary[i].length <= 50dictionary[i] 和 s 只包含小写英文字母。dictionary 中的单词互不相同。
解题思路
比较典型的字符串序列dp问题，类似题目包括LeetCode137、单词拆分，LeetCode472、连接词 。
这类问题的核心点在于思考动态转移过程。
简单举例
以示例二为例，已知s的子字符串"say"不位于dictionary中，而接下来的一个子字符串"hello"位于dictionary中。
s的以"o"为结尾的子字符串"sayhello"可以由以"y"为结尾的子字符串"say"和接下来的"hello"拼接构成。
那么切割"sayhello"的剩余字符数，和切割"say"的剩余字符串相等。
哈希集合进行查找
由于涉及到子串的查找，故将数组dictionary转化为哈希集合word_set，方便在O(1)的复杂度内完成查找。即
word_set = set(dictionary)
动态规划三部曲
我们考虑动态规划三部曲：
dp数组的含义是什么？
构建长度为(n+1)的dp数组dp[i]表示以s[i-1]为结尾的子字符串s[:i]，分割后剩下的字符的最少数目（即题目设问）。dp[0]表示空串""的情况。
动态转移方程是什么？
使用双重循环枚举所有子串s[i:j]，即枚举子串的终点j和起点i。考虑子串s[:i]和子串s[:j]之间的关系（i < j）
如果子串s[i:j]位于word_set中。则s[:j]可以由s[:i]加上s[i:j]构成
故dp[j]可以由dp[i]转移过来。存在dp[j] = min(dp[i], dp[j]) 如果子串s[i:j]不位于word_set中。则可认为s[:j]可以由s[:i]加上子串s[i:j]中的每一个单个字符构成，s[i:j]中一共存在j-i个单字符。
故dp[j]可以由dp[i]+j-i转移过来存在dp[j] = min(dp[i]+j-i, dp[j])
上述逻辑整理为代码即
for j in range(1, (n+1)):
for i in range(j):
if s[i:j] in word_set:
dp[j] = min(dp[i], dp[j])
else:
dp[j] = min(dp[i]+j-i, dp[j])
dp数组如何初始化？
初始化dp[i] = i，表示在初始状态下，每一个字符都进行分割。对于以第i个字符为结尾的子串s[:i]，一共分割出i个字符。
dp = [i for i in range(n+1)]
代码
python
# dp：O(N^3)复杂度
class Solution:
def minExtraChar(self, s: str, dictionary: List[str]) -> int:
word_set = set(dictionary)
n = len(s)
# 初始化长度为(n+1)的dp数组
# dp[i]表示以s[i-1]为结尾的子字符串s[:i]
# 分割后剩下的字符的最少数目
# 初始化dp[i] = i，表示每一个字符都进行分割
dp = [i for i in range(n+1)]
# 遍历结束位置j
for j in range(1, (n+1)):
# 遍历子字符串的开始位置i
for i in range(j):
# 如果子串s[i:j]位于word_set中
# 则s[:j]可以由s[:i]加上s[i:j]构成
# 故dp[j]可以由dp[i]转移过来
if s[i:j] in word_set:
dp[j] = min(dp[i], dp[j])
# 否则，可认为s[:j]可以由s[:i]加上子串s[i:j]中的j-i个单个字符构成
# 故dp[j]可以由dp[i]+j-i转移过来
else:
dp[j] = min(dp[i]+j-i, dp[j])
# 最后返回dp[n]
return dp[n]
java
import java.util.HashSet;
import java.util.Set;
class Solution {
public int minExtraChar(String s, String[] dictionary) {
Set
for (String word : dictionary) {
wordSet.add(word);
}
int n = s.length();
int[] dp = new int[n + 1];
for (int i = 0; i <= n; i++) {
dp[i] = i;
}
for (int j = 1; j <= n; j++) {
for (int i = 0; i < j; i++) {
if (wordSet.contains(s.substring(i, j))) {
dp[j] = Math.min(dp[i], dp[j]);
} else {
dp[j] = Math.min(dp[i] + j - i, dp[j]);
}
}
}
return dp[n];
}
}
cpp
#include
#include
#include
using namespace std;
class Solution {
public:
int minExtraChar(string s, vector
unordered_set
int n = s.length();
vector
for (int i = 0; i <= n; i++) {
dp[i] = i;
}
for (int j = 1; j <= n; j++) {
for (int i = 0; i < j; i++) {
if (wordSet.find(s.substr(i, j - i)) != wordSet.end()) {
dp[j] = min(dp[i], dp[j]);
} else {
dp[j] = min(dp[i] + j - i, dp[j]);
}
}
}
return dp[n];
}
};
时空复杂度
时间复杂度：O(N^3)。枚举子串的终点j和起点i需要双重for循环，复杂度为O(N^2)，获得子串切片s[i:j]的时间复杂度也为O(N)。故总时间复杂度为O(N^3)。N为s的长度。
空间复杂度：O(M)。word_set所需空间，M为dictionary的长度。
华为OD算法/大厂面试高频题算法练习冲刺训练
华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名！目前已服务100+同学成功上岸！ 课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化 每期人数维持在20人内，保证能够最大限度地满足到每一个同学的需求，达到和1v1同样的学习效果！ 60+天陪伴式学习，40+直播课时，300+动画图解视频，300+LeetCode经典题，200+华为OD真题/大厂真题，还有简历修改、模拟面试、专属HR对接将为你解锁 可上全网独家的欧弟OJ系统练习华子OD、大厂真题 可查看链接 大厂真题汇总 & OD真题汇总(持续更新) 绿色聊天软件戳 od1336了解更多
参考文章
您阅读本篇文章共花了：
发表评论