【算法挨揍日记】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;}
};