目录
1.单词拆分
链接： 139. 单词拆分
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例 1：
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。示例 2：
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
注意，你可以重复使用字典中的单词。我有 1 计 bush
public boolean wordBreak(String s, List<String> wordDict) {
return Math.random()<0.5;
}题解：
1.状态表示
- 经验 + 题目要求
- 以 i 位置为结尾，巴拉巴拉
题目要求看字符串能否被字典中单词拼接而成
- dp[i] 表示：[0,i] 区间内的字符串，能否被字典中的单词拼接而成
2.状态转移方程
- 根据最近一个位置的情况，来划分问题
- i的位置是最后一个单词的位置，那最后一个单词是什么样子呢？
- 可能本身就是最后一个单词，或者往前几位然后和 i 位置组成一个单词。又或者前面所有位置构成最后一个单词。
- 这样划分可以把0-i位置字符串划分成两部分，前面部分字符串+后面的单词。
如果我们能确定前面部分字符串能够拼接而成并且后面的单词在字典中，那 0 - i 位置字符串肯定能被拼接而成。
- 但是我们并不知道最后一个单词起始下标在哪里，因此设一个 j 为最后一个单词的起始位置下标。（0 <= j <= i)
- 所以我们的状态转移方程就有了
3.初始化
填第一个位置，dp[j -1]会越界，因此多开一个空间
- 虚拟节点里面的值要保证后序填表正确
- 下标的映射关系
虚拟节点如果给false，整个表不管字符串是什么样子都是false，因此给true。
- 下标的映射关系，对于普通数据我们都是下标减一然后才能找到原数组
- 但是字符串这里有特殊技巧，可以把原始字符前面多加一个辅助字符 ‘ ’ 如 s = ’ ’ + s， 那原始字符串有效字符是不是从下标1开始了，正好就和多开一个空间的dp对应起来了。
- 因为字符串涉及找子串的问题，如果不这样搞，找子串非常头疼，因为下标都不对应了。
4.填表顺序
- 从左往右
5.返回值
- 看整个字符串能否被拼接成功，所以返回dp表最后一个位置，dp[i]
前缀 划分 dp
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict)
{
int n=s.size();
s=' '+s;//解决 下表映射
vector<bool> dp(n+1,false);
dp[0]=true; //多开一个空间 初始化
//! 这个 地方一定要初始化为true
unordered_map<string,int> hash;
for(auto& str:wordDict)
hash[str]++;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=i;j++)
{
string tmp=s.substr(j,i-j+1);
if(dp[j-1]==true
&& hash.count(tmp))
dp[i]=true;
}
}
//双指针 扫描固定切割
// 一个指针找到 可切割位置，就存该点为true
//dp 存状态
return dp[n];
}
};2.环绕字符串中唯一的子字符串
定义字符串 base 为一个 "abcdefghijklmnopqrstuvwxyz" 无限环绕的字符串，所以 base 看起来是这样的：
"...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".
给你一个字符串 s ，请你统计并返回 s 中有多少 不同非空子串 也在 base 中出现。
示例 1：
输入：s = "a"
输出：1
解释：字符串 s 的子字符串 "a" 在 base 中出现。示例 2：
输入：s = "cac"
输出：2
解释：字符串 s 有两个子字符串 ("a", "c") 在 base 中出现。注意 c 要去重
示例 3：
输入：s = "zab"
输出：6
解释：字符串 s 有六个子字符串 ("z", "a", "b", "za", "ab", and "zab") 在 base 中出现。给一个字符串s，返回字符串s中有多少非空子串在 base 中出现。
注意最后结果是去重的！（因为说了字串 要是不同的）
题解
1.状态表示
- 经验 + 题目要求
- 以 i 位置为结尾，巴拉巴拉。
题目要求返回字符串s中有多少非空子串在 base 中出现。
- 以 i 位置为结尾我要先确定 以 i 位置为结尾的所有子串，要么是自己本身，要么就是和前面位置形成的子串
- 接下来找多少个在base中出现。所以状态表示：
- dp[i] 表示：以 i 位置元素为结尾的所有子串里面，有多少个在base中出现
2.状态转移方程
单独本身就是一个子串，和前面元素结合构成子串。所以dp[i]也分这两种情况：
- 长度为1，长度大于1
- 长度为1，在base出现一次
长度大于1，前面元素都有一个共同点，都是以 i - 1 位置元素为结尾形成的子串
那我先找到以 i - 1 位置元素为结尾所有子串在base中出现的次数，然后在加上 i 位置元素构成的子串，看新的子串在base中出现的次数不就可以了吗。
- 而dp[i-1] 就是以 i - 1位置元素为结尾所有子串在base中出现的次数。然后如果 i 位置元素s[i - 1] +1 == s[i] || (s[i - 1] == z && s[i] ==a)说明长度大于1以 i 位置结束的字符串也在base出现了
- 出现次数是dp[i - 1]，不能在后面 + 1！
- 前面出现次数加上i位置这个字符次数还是一样的。
3.初始化
- 我们可以把dp表里面的值都初始化为1，首先本身肯定子串。
- 其次初始化为1的话，上面dp表长度为1 填表时就不要在考虑了，只需要看是否满足长度为1的条件就行了。
4.填表顺序
- 从左往右
5.返回值
- 题目要求返回s 中有多少 不同非空子串 也在 base 中出现次数，
而dp[i] 表示：以 i 位置元素为结尾的所有子串里面，有多少个在base中出现。 - 因此返回 dp 表里面所有元素的和。
但是这样并不对！
我们初始化为1之后，这个例子我们最终返回的是3，但是答案最终是2，是去过重的。
思考一下如何去重？相同子串只统计一次！
- 看下面例子，两个字符串都是以c为结尾，dp表里面存的值，肯定是短的子串小，长的子串大。
- 并且长的子串包含了短的子串的，因此长的子串里面统计的次数也包含了短的子串
- 因此当相同字符结尾的dp表里面的值较大的累加上，较小的直接舍去因为里面全都是重复的。
- 可以让长的 dp 覆盖短的 dp
如何保证相同字符结尾的 dp 值，我们取最大的呢？
- 创建一个大小为 26 的数组
- 里面的的值保存相应字符结尾的最大 dp 值即可
最后返回数组里面的和
class Solution {
public:
int findSubstringInWraproundString(string s)
{
int n=s.size();
if(n==1) return 1;
vector<int> dp(n,1);
// 数组 存dp 最大值，进行去重
int a[26]={0}; //a 0
// 初始化第一个字符
a[s[0]-'a'] = 1;
//因为第一个字符本身构成有效子串
//防止被 后面的for i==1 忽略了
for(int i=1;i<n;i++)
{
if(s[i-1]+1==s[i] || (s[i-1]=='z' &&
s[i]=='a'))
//连续的
dp[i]+=dp[i-1];//继承
int tmp=s[i]-'a';
a[tmp]=max(a[tmp],dp[i]);
}
int ret=0;
//借助 数组 存最大来实现去重 很巧妙
for(int i=0;i<26;i++)
{
ret+=a[i];
}
return ret;
}
};初始化第一个字符
a[s[0]-'a'] = 1;
//因为第一个字符本身构成有效子串
//防止被 后面的for i==1 忽略了