学校网站 制作,wordpress 建站 域名,众筹网站建设公司,服务器安装wordpress文章目录 Tag题目来源解题思路方法一#xff1a;动态规划 写在最后 Tag
【动态规划】【字符串】 题目来源
139. 单词拆分 解题思路
方法一#xff1a;动态规划
定义状态
定义 dp[i] 表示字符串 s 前 i 个字符组成的字符串#xff08;s[0, ..., i-1]#xff09;是否能被… 文章目录 Tag题目来源解题思路方法一动态规划 写在最后 Tag
【动态规划】【字符串】 题目来源
139. 单词拆分 解题思路
方法一动态规划
定义状态
定义 dp[i] 表示字符串 s 前 i 个字符组成的字符串s[0, ..., i-1]是否能被空格拆分成若干个在字典中出现的单词。
转移关系
dp[i] 和 dp[j] 以及字符串 s[j, i-1] 有关即有
KaTeX parse error: Expected EOF, got at position 16: dp[i] dp[j] ̲ check(s.substr…
其中 check() 表示判断参数是否在 wordDict 字符串列表中。
base case
dp[0] true表示初始状态即空字符串也在 wordDict 字符串列表中。
最后返回
最后返回 dp[s.size()]即使用 wordDict 字符串列表中的一个或多个单词是否可以拼接出字符串 s。
实现代码
class Solution {
public:bool wordBreak(string s, vectorstring wordDict) {unordered_setstring st;for (const auto word : wordDict) {st.insert(word);}int n s.size();vectorbool dp(n1);dp[0] true;for (int i 1; i n1; i) {for (int j 0; j i; j) {if (dp[j] st.find(s.substr(j, i-j)) ! st.end()) {dp[i] true;break;}}}return dp[n];}
};复杂度分析
时间复杂度 O ( n ) O(n) O(n) n n n 为字符串 s 的长度。我们一共有 O ( n ) O(n) O(n) 个状态需要计算每次计算需要枚举 O ( n ) O(n) O(n) 个分割点哈希表判断一个字符串是否出现在给定的字符串列表需要 O ( 1 ) O(1) O(1) 的时间因此总时间复杂度为 O ( n 2 ) O(n^2) O(n2)。
空间复杂度 O ( n ) O(n) O(n)。 写在最后
如果您发现文章有任何错误或者对文章有任何疑问欢迎私信博主或者在评论区指出 。
如果大家有更优的时间、空间复杂度的方法欢迎评论区交流。
最后感谢您的阅读如果有所收获的话可以给我点一个 哦。
