【算法挨揍日记】day29——139. 单词拆分、467. 环绕字符串中唯一的子字符串
139. 单词拆分
139. 单词拆分
题目描述：
给你一个字符串 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, vector<string>& wordDict) {
unordered_set<string> hash;
for(auto& s : wordDict) hash.insert(s);
int n=s.size();
vector<bool>dp(n+1);
dp[0]=true;
s=' '+s;
for(int i=1;i<=n;i++)
{
for(int j=i;j>=1;j--)
{
if(dp[j-1]==true&&hash.count(s.substr(j,i-j+1)))
{
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 n=s.size();
vector<int>dp(n,1);
for(int i=1;i<n;i++)
{
if(s[i]-1==s[i-1]||(s[i-1]=='z'&&s[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;
}
};