荆州市网站建设,网站后台的网址忘记了,电子商务网站建设百度文库,服务器怎么做网站139. 单词拆分
139. 单词拆分
题目描述#xff1a;
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
注意#xff1a;不要求字典中出现的单词全部都使用#xff0c;并且字典中的单词可以重复使用。 解题思路
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
注意不要求字典中出现的单词全部都使用并且字典中的单词可以重复使用。 解题思路 算法思路 1. 状态表⽰ 对于线性 dp 我们可以⽤「经验 题⽬要求」来定义状态表⽰ i. 以某个位置为结尾巴拉巴拉 ii. 以某个位置为起点巴拉巴拉。 这⾥我们选择⽐较常⽤的⽅式以某个位置为结尾结合题⽬要求定义⼀个状态表⽰ dp[i] 表⽰ [0, i] 区间内的字符串能否被字典中的单词拼接⽽成。 2. 状态转移⽅程 对于 dp[i] 为了确定当前的字符串能否由字典⾥⾯的单词构成根据最后⼀个单词的起始位 置 j 我们可以将其分解为前后两部分 i. 前⾯⼀部分 [0, j - 1] 区间的字符串 ii. 后⾯⼀部分 [j, i] 区间的字符串。 其中前⾯部分我们可以在 dp[j - 1] 中找到答案后⾯部分的⼦串可以在字典⾥⾯找到。 因此我们得出⼀个结论当我们在从 0 ~ i 枚举 j 的时候只要 dp[j - 1] true 并且后⾯部分的⼦串 s.substr(j, i - j 1) 能够在字典中找到那么 dp[i] true 。 3. 初始化 可以在最前⾯加上⼀个「辅助结点」帮助我们初始化。使⽤这种技巧要注意两个点 i. 辅助结点⾥⾯的值要「保证后续填表是正确的」 ii. 「下标的映射关系」。 在本题中最前⾯加上⼀个格⼦并且让 dp[0] true 可以理解为空串能够拼接⽽成。 其中为了⽅便处理下标的映射关系我们可以将字符串前⾯加上⼀个占位符 s s 这 样就没有下标的映射关系的问题了同时还能处理「空串」的情况。 4. 填表顺序 显⽽易⻅填表顺序「从左往右」。 5. 返回值 由「状态表⽰」可得返回 dp[n] 位置的布尔值。 解题代码
class Solution {
public:bool wordBreak(string s, vectorstring wordDict) {unordered_setstring hash;for(auto s : wordDict) hash.insert(s);int ns.size();vectorbooldp(n1);dp[0]true;s s;for(int i1;in;i){for(int ji;j1;j--){if(dp[j-1]truehash.count(s.substr(j,i-j1))){dp[i]true;break;}}}return dp[n];}
};467. 环绕字符串中唯一的子字符串 467. 环绕字符串中唯一的子字符串
题目描述
定义字符串 base 为一个 abcdefghijklmnopqrstuvwxyz 无限环绕的字符串所以 base 看起来是这样的
...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd.....
给你一个字符串 s 请你统计并返回 s 中有多少 不同非空子串 也在 base 中出现。 解题思路 算法思路 1. 状态表⽰ 对于线性 dp 我们可以⽤「经验 题⽬要求」来定义状态表⽰ i. 以某个位置为结尾巴拉巴拉 ii. 以某个位置为起点巴拉巴拉。 这⾥我们选择⽐较常⽤的⽅式以某个位置为结尾结合题⽬要求定义⼀个状态表⽰ dp[i] 表⽰以 i 位置的元素为结尾的所有⼦串⾥⾯有多少个在 base 中出现过。 2. 状态转移⽅程 对于 dp[i] 我们可以根据⼦串的「⻓度」划分为两类 i. ⼦串的⻓度等于 1 此时这⼀个字符会出现在 base 中 ii. ⼦串的⻓度⼤于 1 如果 i 位置的字符和 i - 1 位置上的字符组合后出现在 base 中的话那么 dp[i - 1] ⾥⾯的所有⼦串后⾯填上⼀个 s[i] 依旧在 base 中出 现。因此 dp[i] dp[i - 1] 。 综上 dp[i] 1 dp[i - 1] 其中 dp[i - 1] 是否加上需要先做⼀下判断。 3. 初始化 可以根据「实际情况」将表⾥⾯的值都初始化为 1 。 4. 填表顺序 显⽽易⻅填表顺序「从左往右」。 5. 返回值 这⾥不能直接返回 dp 表⾥⾯的和因为会有重复的结果。在返回之前我们需要先「去重」 i. 相同字符结尾的 dp 值我们仅需保留「最⼤」的即可其余 dp 值对应的⼦串都可以在 最⼤的⾥⾯找到 ii. 可以创建⼀个⼤⼩为 26 的数组统计所有字符结尾的最⼤ dp 值。 最后返回「数组中所有元素的和」即可。 解题代码
class Solution {
public:int findSubstringInWraproundString(string s) {int ns.size();vectorintdp(n,1);for(int i1;in;i){if(s[i]-1s[i-1]||(s[i-1]zs[i]a))dp[i]dp[i-1]1;}// 2. 计算每⼀个字符结尾的最⻓连续⼦数组的⻓度int hash[26] { 0 };for(int i 0 ; i n; i)hash[s[i] - a] max(hash[s[i] - a], dp[i]);// 3. 将结果累加起来int sum 0;for(auto x : hash) sum x;return sum;}
};
