本文主要是介绍【七十一】【算法分析与设计】467. 环绕字符串中唯一的子字符串,940. 不同的子序列 II,子串的划分,子序列的划分,区间划分---递推，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
467. 环绕字符串中唯一的子字符串
定义字符串
base为一个"abcdefghijklmnopqrstuvwxyz"无限环绕的字符串，所以base看起来是这样的：
"...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".给你一个字符串
s，请你统计并返回s中有多少 不同非空子串 也在base中出现。示例 1：
输入：s = "a" 输出：1 解释：字符串 s 的子字符串 "a" 在 base 中出现。
示例 2：
输入：s = "cac" 输出：2 解释：字符串 s 有两个子字符串 ("a", "c") 在 base 中出现。
示例 3：
输入：s = "zab" 输出：6 解释：字符串 s 有六个子字符串 ("z", "a", "b", "za", "ab", and "zab") 在 base 中出现。
提示：
1 <= s.length <= 10(5)s 由小写英文字母组成
1.
子串的划分,以某个位置结尾的子串,进行子串的划分.
把所有位置结尾的子串中出现在base个数记录下来即可.
2.
只需要记录以某位置结尾往前最长的连续子串长度即可.
例如abcde,bcde,cde,de,e,最长的连续子串长度是5,依次对应五个数量.
3.
子串的划分----分治
#include <bits/stdc++.h> // 引入常用的头文件
using namespace std;class Solution {
public:using ll = long long; // 定义类型别名ll，表示长整型long longstring s; // 定义字符串s，存储输入字符串vector<ll> dp; // 使用动态规划存储中间结果，dp[i]存储以s[i]结尾的子串的合法子串数量vector<ll> count; // 记录每个字母为结束字符的最长子串长度// 初始化函数，清空并重设dp和count数组void solveinit() {dp.clear(); // 清空dp数组dp.resize(s.size(), -1); // 重设dp数组大小，初始值为-1count.clear(); // 清空count数组count.resize(26); // 重设count数组大小，大小为26（26个字母）}// 深度优先搜索函数，用于计算以第i个字符结束的子串的合法子串数量ll dfs(ll i) {if (dp[i] != -1) // 如果dp[i]已计算过，直接返回结果return dp[i];if (i - 1 >= 0) { // 如果不是第一个字符，可以考虑前一个字符if (s[i] != 'a') { // 当前字符不是'a'时if (s[i - 1] == s[i] - 1) { // 如果前一个字符正好是当前字符的前一个字母dp[i] = dfs(i - 1) + 1; // 递归计算前一个字符，并加上当前字符形成的新的子串} else {dp[i] = 1; // 否则，当前字符自成一组}} else {if (s[i - 1] == 'z') { // 当前字符是'a'且前一个字符是'z'dp[i] = dfs(i - 1) + 1; // 递归计算前一个字符，并加上当前字符形成的新的子串} else {dp[i] = 1; // 否则，当前字符自成一组}}} else {dp[i] = 1; // 如果是第一个字符，只有当前字符自身一个子串}return dp[i]; // 返回以s[i]结尾的合法子串数量}// 主函数，计算字符串s中有多少不同非空子串也在环绕字符串base中出现int findSubstringInWraproundString(string _s) {s = _s; // 存储输入字符串solveinit(); // 初始化dp和count数组for (ll i = 0; i < s.size(); i++) {dfs(i); // 对每个字符调用dfs函数，计算以每个字符结尾的子串数量}ll ans = 0;vector<bool> visited(26); // 标记数组，记录每个字符是否被访问过for (ll i = 0; i < s.size(); i++) {int index = s[i] - 'a'; // 当前字符对应的索引count[index] = max(count[index], dp[i]); // 更新以当前字符结尾的最大子串数量}for (ll i = 0; i < 26; i++) {ans += count[i]; // 累加每个字母对应的最长子串数量}return ans; // 返回结果}
};
940. 不同的子序列 II
给定一个字符串
s，计算s的 不同非空子序列 的个数。因为结果可能很大，所以返回答案需要对10^9 + 7取余 。字符串的 子序列 是经由原字符串删除一些（也可能不删除）字符但不改变剩余字符相对位置的一个新字符串。
例如，
"ace"是"abcde"的一个子序列，但"aec"不是。示例 1：
输入：s = "abc" 输出：7 解释：7 个不同的子序列分别是 "a", "b", "c", "ab", "ac", "bc", 以及 "abc"。
示例 2：
输入：s = "aba" 输出：6 解释：6 个不同的子序列分别是 "a", "b", "ab", "ba", "aa" 以及 "aba"。
示例 3：
输入：s = "aaa" 输出：3 解释：3 个不同的子序列分别是 "a", "aa" 以及 "aaa"。
提示：
1 <= s.length <= 2000
s仅由小写英文字母组成
1.
假设s长度为n.
区间[0,n-1]的字符串的不同的子序列个数是多少.
区间[0,n-2]的字符串的不同的子序列个数是多少.
可以选择由[0,n-2]区间字符串的不同子序列个数多少推导出[0,n-1]的字符串的不同的子序列个数是多少.
因为新增的子序列是[0,n-2]区间所有子序列后面全部加上n-1位置的字符所组成的子序列加上n-1位置单独的字符子序列.
只需要完成新增子序列与老子序列的去重操作即可.
新增子序列都是以n-1位置结尾的子序列,一定是包含了所有的以n-1字符结尾的可能性.
所以老子序列中去掉以n-1字符结尾的可能性加上其他字符结尾的个数即可.
2.
子序列的划分----分治
长度的划分,递推,增加的子序列很好计算.
class Solution {
public:using ll = long long; // 定义类型别名 ll，表示长整型 long longstring s; // 用于存储输入的字符串vector<ll> count; // 使用一个数组来统计每个字符作为子序列结尾的不同子序列个数const ll MOD = 1e9 + 7; // 定义常量 MOD，取值为 10^9 + 7，用于结果的模运算void solveinit() {count.clear(); // 清空 count 数组count.resize(26); // 将 count 数组大小重新设置为26（对应26个英文字母）}int distinctSubseqII(string _s) {s = _s; // 将传入的字符串赋值给成员变量 ssolveinit(); // 调用初始化函数，准备 count 数组for (ll i = 0; i < s.size(); i++) { // 遍历字符串 s 的每个字符ll all = 0; // 初始化 all 变量，用来统计到当前字符为止的所有可能子序列的数量for (ll j = 0; j < count.size(); j++) { // 遍历 count 数组，累加之前所有字符的子序列总数all = (all + count[j]) % MOD; // 将累加结果进行模运算，防止溢出}ll index = s[i] - 'a'; // 计算当前字符在 count 数组中的索引位置count[index] = (all + 1) % MOD; // 更新当前字符的子序列数。加1是因为当前字符本身也是一个子序列}ll ans = 0; // 初始化答案变量，用来存储最终的不同子序列总数for (ll i = 0; i < count.size(); i++) { // 遍历 count 数组，将所有字符的子序列数累加ans = (ans + count[i]) % MOD; // 累加的同时进行模运算，防止溢出}return ans; // 返回最终计算的结果}
};
结尾
最后，感谢您阅读我的文章，希望这些内容能够对您有所启发和帮助。如果您有任何问题或想要分享您的观点，请随时在评论区留言。
同时，不要忘记订阅我的博客以获取更多有趣的内容。在未来的文章中，我将继续探讨这个话题的不同方面，为您呈现更多深度和见解。
谢谢您的支持，期待与您在下一篇文章中再次相遇！
这篇关于【七十一】【算法分析与设计】467. 环绕字符串中唯一的子字符串,940. 不同的子序列 II,子串的划分,子序列的划分,区间划分---递推的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
