建设银行网站开通查询密码,测网站打开的速度的网址,保险网站导航,医院系统网站建设文章目录 题目描述解题思路简单举例哈希集合进行查找动态规划三部曲 代码pythonjavacpp时空复杂度 华为OD算法/大厂面试高频题算法练习冲刺训练 题目描述
给你一个下标从 0 开始的字符串 s 和一个单词字典 dictionary 。你需要将 s 分割成若干个 互不重叠 的子字符串#xff… 文章目录 题目描述解题思路简单举例哈希集合进行查找动态规划三部曲 代码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数组的含义是什么
构建长度为(n1)的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, (n1)):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(n1)]代码
python
# dpO(N^3)复杂度
class Solution:def minExtraChar(self, s: str, dictionary: List[str]) - int:word_set set(dictionary)n len(s)# 初始化长度为(n1)的dp数组# dp[i]表示以s[i-1]为结尾的子字符串s[:i]# 分割后剩下的字符的最少数目# 初始化dp[i] i表示每一个字符都进行分割dp [i for i in range(n1)]# 遍历结束位置jfor j in range(1, (n1)):# 遍历子字符串的开始位置ifor 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) {SetString 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, vectorstring dictionary) {unordered_setstring wordSet(dictionary.begin(), dictionary.end());int n s.length();vectorint 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动画图解视频300LeetCode经典题200华为OD真题/大厂真题还有简历修改、模拟面试、专属HR对接将为你解锁 可上全网独家的欧弟OJ系统练习华子OD、大厂真题 可查看链接 大厂真题汇总 OD真题汇总(持续更新) 绿色聊天软件戳 od1336了解更多
