计算所有子字符串的权重和最多为 K
简介
在本教程中，我们讨论计算给定字符串中子字符串的权重和最多为 K 的问题。为了实现问题陈述，我们考虑使用字符串 S 来生成子字符串和一些 k 值。字符权重是预定义的整数值，我们考虑一些 K 值，如 2、3 或任何值。我们只计算总权重等于 K 值的子字符串。
字符的权重有两种不同的定义方式 −
当以任意顺序为字符串定义权重时。
当从 1 开始按字母顺序定义权重时。
示例 1
String = "aba" K = 5
输出
权重最多为 5 的可能子字符串为:6
解释
使用输入字符串和 k 的值，我们从 1 开始按字母顺序获取字符的权重。 'a' 为 1，'b' 为 2，'c' 为 3，'d' 为 4，依此类推。一共有 6 个可能的子字符串，其权重之和最多为 K。子字符串如下 −
a ab aba b ba a
示例 2
String = "abcd" Weight = "1234" K = 6
输出
权重最多为 6 的子字符串数量为 7。
解释
在上面的输入字符串中，我们初始化所有字符的权重。k 的值为 6。字符串"abcd"的字符权重分别为 1234。有 7 个可能的子字符串，其权重之和最多为 k。这些子字符串如下 -
a ab ab cb bc c d
C++ 库函数
length() − 它是一个字符串类库函数，定义在标准 C++ 库中。它返回字符串的长度(以字节为单位)。
string_name.length();
vector − 它是 C++ 中的动态数组。它提供简单高效的数组删除和更新操作。它可以是整数或字符串类型。
vector<data_type> vector_name;
unordered_set() − 它是 C++ 中的一个容器，可以随机存储元素，没有任何定义的顺序。它有助于快速检索其存储的元素。
unordered_set <data_type> unordered_set_name;
算法
初始化输入字符串。
从 1 开始按字母顺序考虑字符的权重。
初始化 k 的值(最大可能权重)。
遍历所有权重最多等于 k 的子字符串。
计数器变量计数所有权重最多为 k 的子字符串。
打印 k 的结果。
示例 1
在这里，我们使用 C++ 实现问题陈述。用户定义函数"countSubstrings()"用于计数所有权重和最多等于 K 的子字符串。子串权重从 1 开始，按字母顺序分配。
#include <iostream>
#include <string>
using namespace std;
int countSubstrings(const string& s, int K) {
int cnt = 0;
int l = s.length();
for (int x = 0; x < l; x++){
int sum = 0;
for (int y = x; y < l; y++) {
// 计算从索引 i 到 j 的子字符串的权重
sum += s[y] - 'a' + 1; // 假设权重基于字母顺序
// 如果权重之和小于或等于 K，则增加计数
if (sum <= K){
cnt++;
}
}
}
return cnt;
}
int main() {
string s = "aba"; // 预定义字符串
int K = 5; // 预定义最大权重
int Output = countSubstrings(s, K);
cout << "权重和最多为 " << K << " 的子字符串计数: " << Output << endl;
// 生成子字符串
cout << "权重和最多为 " << K << " 的子字符串:" << endl;
int l = s.length();
for (int x = 0; x < l; x++) {
for (int y = x; y < l; y++){
string substrg = s.substr(x, y - x + 1);
int weight = 0;
for (char ch : substrg){
weight += ch - 'a' + 1;
}
if (weight <= K) {
cout << substrg << endl;
}
}
}
return 0;
}
输出
计算权重和最多为 5 的子字符串数量:6 计算权重和最多为 5 的子字符串数量: a ab aba b ba a
示例 2
我们使用 C++ 实现该任务。初始化一个字符串和一个加权字符串。权重字符串元素用作输入字符串权重。使用嵌套循环使用权重字符串生成子字符串。计算权重和最多为 K 的子字符串数量。
#include <iostream>
#include <unordered_set>
using namespace std;
//用户定义函数来生成子字符串
void generateSubstrings(string s, string weights, int K, unordered_set<string>& substrings){
//获取输入字符串的长度
int l = s.length();
//循环生成所有子字符串
for (int x = 0; x < l; x++){
for (int y = 1; y <= l - x; y++) {
string substring = s.substr(x, y);
//求和变量以计算权重
int sumString = 0;
for (char c : substring){
int post = c - 'a';
sumString += weights[post] - '0';
}
//当字符串 sun 小于等于 K 时，插入子字符串
if (sumString <= K){
substrings.insert(substring);
cout << substring << endl;
}
}
}
}
//代码控制器
int main(){
//初始化字符串
string S = "abcd";
//初始化权重变量
string W = "1234";
//初始化 K 的值
int K = 6;
unordered_set<string> substrings;
//调用函数
generateSubstrings(S, W, K, substrings);
cout << "权重最多为 " << K << "的子字符串数量:" << substrings.size() << endl;
return 0;
}
输出
a ab abc b bc c d 权重最多为 6 的子字符串的计数:7
结论
在本教程中，我们计算所有权重最多为 k 的子字符串。我们使用两种不同的方法实现了该任务。在第一种情况下，我们使用加权字符串来初始化输入字符串字符的权重。在第二种情况下，权重按字母顺序定义，从 1 开始。使用 C++ 实现这两种情况，并使用嵌套循环概念。
在编写 C++ 代码以了解问题陈述需求并计算子字符串之前，用一些示例演示了问题。
