【Py/Java/C++三种语言详解】LeetCode每日一题240109【动态规划】LeetCode2707题、字符串中的额外字符
题目描述
给你一个下标从 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
中的单词互不相同。
解题思路
比较典型的字符串序列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<String> wordSet = new HashSet<>();
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 <vector>
#include <string>
#include <unordered_set>
using namespace std;
class Solution {
public:
int minExtraChar(string s, vector<string>& dictionary) {
unordered_set<string> wordSet(dictionary.begin(), dictionary.end());
int n = s.length();
vector<int> dp(n + 1, 0);
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
了解更多
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!