极客笔记C++ 查找所有子字符串，其中包含偶数个1，并且其反转也存在于给定的字符串中
在这个问题中，我们需要准备给定二进制字符串的一组唯一子字符串，并从该组中去除包含偶数个1和其反转存在于该组中的字符串。
我们可以用两种方法解决这个问题。第一种方法是找到给定二进制字符串的所有子字符串，检查是否有任何子字符串包含偶数个1，并且其反转存在，并将反转的字符串从集合中删除。
另一种方法是通过比较给定字符串中奇偶校验位的总数。
问题陈述 – 我们有一个包含偶数个1的二进制字符串str。我们需要准备给定二进制字符串的所有唯一子字符串的集合。之后，我们需要考虑集合中包含偶数个1的长度为n的子字符串。如果子字符串的反转也存在于集合中，则从集合中删除反转的子字符串。在输出中，打印包含唯一子字符串的集合的大小。
示例
输入
str = "01010"
输出结果
8
解释
- 唯一子字符串的集合为[0, 1, 01, 010, 0101, 01010, 10, 101, 1010]。总共有9个子字符串。
-
0101包含偶数个1，并且它的翻转也存在于集合中。因此，我们将删除它的翻转，即1010，从给定的集合中。
-
最终集合将为[0, 1, 01, 010, 0101, 01010, 10, 101]。最终集合的大小为8。
输入
str = '1010'
输出
7
解释
- 唯一的子字符串是[1, 10, 101, 1010, 0, 01, 010]。
-
对于任何包含偶数个1的字符串，它的反转在集合中不存在。因此，我们不需要从集合中移除任何字符串。
-
最终输出与原始集合的大小相同。
输入
str = "111"
输出
3
- 唯一的子串是[1，11，111]。
-
只有含有偶数个1的字符串是11。
-
11的逆序也是11。所以，我们不需要从集合中移除它，答案是3。
方法1
在这个方法中，我们将创建一个包含给定二进制字符串的所有唯一子串的集合。之后，我们将遍历集合，如果我们找到任何包含偶数个1并且它的逆序也存在于集合中的字符串，我们将从集合中移除该字符串。
算法
步骤1 - 定义一个名为’subStrings’的集合来存储唯一的子串。
步骤2 - 从第0个索引开始遍历字符串。在循环内部，定义一个名为’temp’的变量并初始化为空字符串。
步骤3 - 使用另一个嵌套循环，从第p个索引开始迭代，并将第q个字符追加到’temp’字符串中。
步骤4 - 将’temp’字符串插入集合中。
步骤5 - 使用迭代器遍历子串集合。
步骤7 - 如果当前字符串中的1的总数是偶数，逆置’temp’字符串，并检查逆置的’temp’是否存在于集合中。
步骤8 - 如果逆置字符串存在，则移除逆置字符串。
步骤9 - 返回集合的大小。
示例
#include <bits/stdc++.h>
using namespace std;
int getSize(string str) {
// unordered set to store all substrings of a given string
unordered_set<string> subStrings;
// finding all substrings of a given string
for (int p = 0; p < str.length(); p++) {
string temp = "";
for (int q = p; q < str.length(); q++) {
temp += str[q];
subStrings.insert(temp);
}
}
// Check if any string contains an even number of 1's and its reverse exists in the set, then remove the string.
for (auto it = subStrings.begin(); it != subStrings.end(); it++) {
string temp = *it;
// count the number of 1's in the string
int cnt1s = 0;
for (int i = 0; i < temp.length(); i++) {
if (temp[i] == '1')
cnt1s++;
}
// If count of 1's is even
if (cnt1s % 2 == 0) {
// reverse substring
reverse(temp.begin(), temp.end());
// check if reverse exists in the set, remove it.
if (temp != *it && subStrings.find(temp) != subStrings.end()) {
subStrings.erase(temp);
}
}
}
return subStrings.size();
}
int main() {
string str = "01010";
cout << "The size of the set containing unique strings is " << getSize(str);
return 0;
}
输出
The size of the set containing unique strings is 8
时间复杂度 - O(N^4)，因为O(N^2)用于遍历所有子字符串，并且我们使用嵌套循环遍历集合。
空间复杂度 - O(N^2)，用于存储集合中的所有子字符串。
方法2
在这个方法中，我们将创建一个包含3个参数的列表：子字符串长度，偶数个1和奇数个1。字符串的反向也具有相同的长度，偶数个1和奇数个1。如果我们将唯一的对添加到列表中，我们可以找到所有符合列表条件的子字符串。
算法
第1步 - 定义’ setList ‘向量集的类型，因为我们需要存储唯一对。
第2步 - 开始遍历字符串。同时，定义cnt1s，even1s和odd1s变量，并初始化为零。
第3步 - 开始遍历子字符串。如果第q个索引处的字符是’1’，则将cnt1s增加1。
第4步 - 否则，如果cnt1s是偶数，则增加even1s。否则，增加odd1s。
第5步 - 获取子字符串的长度，并在创建列表后将len、even1s和odd1s存储到集合中。
第6步 - 返回列表的大小。
示例
#include <bits/stdc++.h>
using namespace std;
int getSize(string str) {
// set to store the unique strings
set<vector<int>> setList;
// Iterate the string
for (int p = 0; p < str.length(); p++) {
// Required variables
int cnt1s = 0, even1s = 0, odd1s = 0;
for (int q = p; q < str.length(); q++) {
// Count the counts of 1's
if (str[q] == '1') {
cnt1s++;
} else {
// If the count of 1's is even, increment even1s. Otherwise, increment odd1s.
if (cnt1s % 2 == 0) {
even1s++;
} else {
odd1s++;
}
}
// get substring length
int len = q - p + 1;
// Insert the substring in the set
vector<int> temp;
temp.push_back(len);
temp.push_back(even1s);
temp.push_back(odd1s);
setList.insert(temp);
}
}
return setList.size();
}
int main() {
string str = "01010";
cout << "The size of the set containing unique strings is " << getSize(str);
return 0;
}
输出
The size of the set containing unique strings is 8
时间复杂度 - O(N^2)，因为我们创建了所有的子字符串。
空间复杂度 - O(N*N)，用于存储集合中的配对字符串。
对于初学者来说，第二种解决方案可能会更难理解，但如果我们说反转字符串具有相同的长度和奇偶校验位，那么它就非常容易理解。第一种方法的时间复杂度更高。因此，使用第二种方法来解决问题更好。