当前位置：极客笔记 > C++ > C++ 精选笔记 > C++ 在执行给定操作后计算的不同可能字符串的数量

C++ 在执行给定操作后计算的不同可能字符串的数量

C++ 在执行给定操作后计算的不同可能字符串的数量

确定通过对字符串执行一组给定操作可以获得的唯一字符串的数量是计算机科学和数学中的常见挑战。可以对字符串执行多种操作，包括字符删除、交换或字符串反转。目标是计算通过这些操作可以实现的不同输出字符串的总数，而不考虑其顺序。解决这个问题的技巧包括动态规划、递归和组合数学等，这取决于所进行的特定操作的性质。

方法

要计算执行给定操作后的不同可能字符串的数量，可以使用以下方法:

  • 暴力方法。

  • 集合方法。

  • 动态规划。

  • 组合方法。

方法1：暴力方法

该函数允许您创建通过执行指定的过程可以生成的任何字符串。然后，计算获得的不同字符串计数。对于大型输入，此方法可能耗时且低效。

语法

可以按照以下步骤进行该方法-

string_count = 0
for operation_combination in all_possible_combinations(operations_list):
   new_string = apply_operations(original_string, operation_combination)
   if is_distinct(new_string):
   string_count += 1
return string_count

步骤

步骤1 − 从头开始创建一个集合，用于保存不同的字符串。

步骤2 − 通过提供的过程生成每一个可能的字符串。

步骤3 − 验证每个创建的字符串是否已经存在于不同字符串的集合中。

步骤4 − 如果字符串还不在集合中，则需要将其添加到集合中。

步骤5 − 重复执行步骤2-4，直到生成和验证所有可能的字符串。

步骤6 − 将不同可能的字符串的数量作为唯一字符串集合的长度返回。

示例1

我们有一个C++的暴力方法示例−

在这个示例中，我们将以输入字符串s作为一个向量的起始值。通过更改向量中每个字符串的字符来进行提供的操作。我们重复这个过程k次，将产生的每个字符串存储在向量中。最后，我们使用unique函数对向量进行排序，并确定有多少不同的字符串。响应将作为最终计数返回。

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int countDistinctStrings(string s, int n, int k) {
   vector<string> v;
   v.push_back(s);
   for(int i=0; i<k; i++) {
      int len = v.size();
      for(int j=0; j<len; j++) {
        string temp = v[j];
         for(int x=0; x<n; x++) {
            for(int y=x+1; y<n; y++) {
               if(temp[x] != temp[y]) {
                  swap(temp[x], temp[y]);
                  v.push_back(temp);
                  swap(temp[x], temp[y]);
              }
            }
         }
      }
   }
   sort(v.begin(), v.end());
   int cnt = unique(v.begin(), v.end()) - v.begin();
   return cnt;
} 
int main() {
   string s = "abb";
   int n = s.length();
   int k = 2;
   int ans = countDistinctStrings(s, n, k);
   cout << "Distinct strings after " << k << " operations: " << ans << endl;
   return 0;
}

输出

Distinct strings after 2 operations: 3

方法2：集合方法

在这个方法中，通过执行指定的操作获得的所有不同字符串可以存储在一个集合中。可以在生成字符串时将其添加到集合中（如果它尚不存在）。可以计算集合的大小以确定创建每个可能的字符串后的不同字符串数。

语法

在使用该方法计算给定操作后的可能不同字符串时，语法通常包括以下步骤：

  • 初始化一个空集合来存储不同的字符串。
distinct_strings = set ()
  • 将给定操作应用于原始字符串，生成所有可能的字符串。
def generate_strings(original_string, operations):
return new_strings
  • 将每个生成的字符串添加到集合中以确保唯一性。
for string in generate_strings(original_string, operations):
   distinct_strings.add(string)
  • 最后，检索不同字符串的数量。
count = len(distinct_strings)

这个基于集合的解决方案利用了集合自动消除重复项的特性，仅存储不同的字符串。在对原始字符串应用指定的程序后，可以通过使用这种方法有效地计算可能的字符串数量。

步骤

步骤1 - 从头开始创建一个集合，用于保存所有可达到的不同字符串。

步骤2 - 将初始字符串S包含在集合中。

步骤3 - 对列表中的每个操作（L，R，X）：

  • 对集合中的每个唯一字符串 –
    • 制作字符串的副本。

    • 在复制的字符串中，将索引L到R（包括L和R）的字符更改为X。

    • 将复制的字符串添加到集合中。

步骤4 - 提供集合”distinct_strings”的大小。

示例2

为了存储所有长度为k的不同子字符串，我们使用这个代码创建一个空的distinctStrings集合。通过循环遍历给定的字符串s，我们创建了每个可行的长度为k的子字符串。然后，不同字符串的集合随着每个子字符串的增加而更新。集合的大小告诉我们在插入所有子字符串后，总共有多少个不同的潜在字符串。这个值是函数的输出，我们返回它。

在上面的示例中，字符串s为”abbabc”，目标是确定长度为k=2的唯一字符串有多少种可能。程序返回值为3，表示通过将指定的程序应用于字符串s，可以创建3个长度为2的唯一字符串。

#include<bits/stdc++.h>
using namespace std;

// Function to count the distinct possible strings
int countDistinctStrings(int n, int k, string s) {
   set<string> distinctStrings; // Create an empty set to store distinct strings

   // Create all possible sub strings of length k and insert them into the set
   for (int i = 0; i <= n-k; i++) {
      string temp = s.substr(i, k);
      distinctStrings.insert(temp);
   }

   // Calculate the total number of distinct strings
   int ans = distinctStrings.size();

   return ans;
}

// Driver code
int main() {
   int n = 6, k = 2; // Given values of n and k
      string s = "abbabc"; // Given string

   // Call the countDistinctStrings function and print the result
   int distinctStrings = countDistinctStrings(n, k, s);
   cout << "The number of distinct possible strings is: " << distinctStrings << endl;

   return 0;
}

输出

The number of distinct possible strings is: 4

方法3：动态规划

这种方法使用动态规划有效地计算唯一字符串的数量。在特定操作次数后获得的不同字符串数量可以由一个你可以定义的状态来表示。使用递归关系来根据之前的状态计算后续状态的不同字符串数量。对于大型输入，这种方法可能更有效。

语法

C++中动态规划方法的示例语法-

int countDistinctStrings(int n, vector& operations) {
  • 初始化表或数组
vector<int> dp(n + 1, 0);
  • 设置基本情况
dp[0] = 1;
  • 迭代子问题
for (int i = 1; i <= n; i++) {
  • 根据先前子问题计算值
for (int op : operations) {
   if (i >= op) {
      dp[i] += dp[i - op];
   }
}
}
  • 返回最终答案
return dp[n];
}

步骤

以下是使用动态规划算法来计算在执行给定操作后可能字符串的不同个数的算法 −

步骤1 − 初始化二维数组DP[n][k]，其中n表示原始字符串的长度，k表示允许的操作次数。使用原始字符串的前i个字符和j个操作可以创建的不同字符串的数量用值DP[i][j]表示。

步骤2 − 因为只有使用零个字符和零个操作可以创建一个字符串，将DP[0][0]设为1。

步骤3 − 程序应将DP[i][j]设置为DP[x][j-1]的累积和，其中x表示操作j中最后修改的字符的索引，范围从0到i-1。如果没有之前的操作，让x为零。

步骤4 − 计算DP[i][j]时，从0到i-1减去所有DP[x][j-1]的和，其中x表示在第j次操作中替换为相同字符的最后一个字符。如果没有之前的操作，设x为0。

步骤5 − 返回DP[n][k]的值，表示通过将起始字符串的所有n个字符与k个操作相结合可以创建多少个独特的字符串。

示例1

使用C++的动态规划来计算遵循指定操作的不同潜在字符串的示例 −

此示例中的countDistinctStrings函数有四个输入参数：n、k、x和y。X和Y是模数值，而n表示字符串的长度，k表示字符串中可以包含的连续1的最大数量。

该函数将不同长度i和连续1的数量j的字符串数量存储在名为dp的二维数组中。使用memset方法将数组初始化为0。

然后，根据先前的长度i-1和连续1的数量j-1更新dp数组，函数遍历每个长度i和连续1的数量j。如果连续1的数量等于k，则使用模y代替模x。

然后，该函数输出dp [n％2] [k]，这是可以具有长度n且最多具有k个连续1的独特字符串的数量。

在主函数中调用countDistinctStrings函数，使用指定的n、k、x和y的值。然后，控制台打印出最终的计数。

#include <iostream>
#include <cstring>
using namespace std;

int countDistinctStrings(int n, int k, int x, int y) {
   int dp[2][k + 1];
   memset(dp, 0, sizeof(dp));
   dp[0][0] = 1;

   for (int i = 1; i <= n; i++) {
      int cur = i % 2;
      int prev = (i - 1) % 2;

      for (int j = 0; j <= k; j++) {
         dp[cur][j] = dp[prev][j];

         if (j > 0) {
            dp[cur][j] += dp[prev][j - 1];
            dp[cur][j] %= x;
         }   

         if (j == k) {
            dp[cur][j] -= dp[prev][j - 1];
            dp[cur][j] %= y;
            dp[cur][j] += y;
            dp[cur][j] %= y;
         }
      }
   }
   return dp[n % 2][k];
}

int main() {
   int n = 4;
   int k = 2;
   int x = 1000000007;
   int y = 998244353;

   int count = countDistinctStrings(n, k, x, y);

   cout << "Count of distinct possible strings: " << count << endl;

   return 0;
}

输出

Count of distinct possible strings: 0

方法4：组合方法

这种方法可以利用组合数学来直接计算不同字符串的数量。例如，如果可以在字符串的末尾添加’a’或’b’，可以使用’a’和’b’组合的公式来计算生成的不同字符串的数量。这种策略在处理最小输入数量和过程计数时可能会有帮助。

语法

在完成上述操作后，组合方法用于计算不同潜在字符串的语法如下：

  • 命名操作组：
operations are op1, op2,..., opk.
  • 指定限制条件 –
restrictions = "c1, c2,..., cn"
  • 确定有多少个不同的字符串：-
count is equal to f(operations, constraints),

其中f是一个组合函数，用于确定可以从给定的操作和限制产生多少个唯一的字符串。

根据操作和情况的不同，可以使用不同的函数f的实现。为了列举潜在的字符串，通常需要利用组合公式，如排列、组合或生成函数。

步骤

第1步 - 将第一个字符串“s”添加到字符串集合S中。

第2步 - 对于每个操作（li，ri），执行以下操作：

  • 为S中的每个字符串t创建一个新的字符串u，通过翻转子字符串s[li:ri]中的字符。

  • 将字符串“u”包含在集合“S”中。

第3步 - 提供集合S的大小。

第4步 - 算法完成。

该算法的时间复杂度为O(k * 2n)，其中n是初始字符串的长度，k是操作的数量。这是因为在最坏情况下可能有2n个不同的字符串，每个字符串都可以经过操作产生k * 2n个字符串。然而，总体上可能有更少的不同字符串，并且通过不生成重复字符串可以提高该过程。

示例4

一个示例展示了如何使用C ++实现组合方法来计算应用操作后可能的字符串数量。

在这种情况下，有一个长度为n=5的字符串，可以使用k=2个过程生成唯一的字符串。操作由整数向量表示，其中1表示在两个相邻字符之间放置一个字符，0表示在两个零之间插入一个字符。将计算这些操作后得到的唯一字符串的数量。

count_possible_strings()函数的输入参数为字符串长度n，操作的数量k和操作向量。然后，使用组合数公式来确定在每个操作之后可以形成的潜在字符串的数量，同时循环遍历过程。在完成所有操作后，将生成的潜在字符串数量相加，并返回总计数。

一个有用的函数binomial_coefficient()使用公式n！/（k！*（n-k）！）计算二项式系数nCk。为了防止溢出，使用循环分别计算分子和分母。

我们输入参数值并在主代码中调用count_possible_strings()方法，然后返回结果。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Helper function to calculate the binomial coefficient nCk
int binomial_coefficient(int n, int k) {
   if (k > n - k) k = n - k;
   int res = 1;
   for (int i = 0; i < k; i++) {
      res *= (n - i);
      res /= (i + 1);
   }
    return res;
}
// Function to count the distinct possible strings after performing given operations
int count_possible_strings(int n, int k, vector<int>& operations) {
   int num_ones = 1, num_zeros = 0, res = 0;
   for (int i = 0; i < operations.size(); i++) {
      if (operations[i] == 1) {
         res += binomial_coefficient(num_ones + num_zeros, num_ones);
         num_ones++;
      } else {
         num_zeros++;
      }
   }
   res += binomial_coefficient(num_ones + num_zeros, num_ones);
   return res;
}
// Driver code
int main() {
   int n = 5, k = 2;
   vector<int> operations = {1, 0, 1};
   int count = count_possible_strings(n, k, operations);
   cout << "Count of distinct possible strings = " << count << endl;
   return 0;
}

输出

Count of distinct possible strings = 8

结论

总之，确定由特定操作产生的不同潜在字符串数量是一个具有多种解决方案的具有挑战性的问题。数学概念，如排列组合，以及算法技术，如动态规划，可以用于快速计算给定操作生成的唯一字符串的数量。然而，这些算法的执行时间和内存需求可能会随着问题规模的增加和添加操作而呈指数级增长。因此，在决定使用哪种方法时，需要考虑每个问题实例，以在保持平衡的同时提供更高的效率和准确性。

Camera课程

Camera API2 教程

API2 教程
Camera 性能教程

Perf 教程
Camera Native Framework 教程

Native FW 教程
Camera QCOM ISP 教程

ISP 教程
Camera QCOM Sensor 教程

Sensor 教程

Python教程

Python 教程

Python 教程
NumPy 教程

NumPy 教程
Django 教程

Django 教程

Java教程

Java 教程

Java 教程

Web教程

JavaScript 教程

JavaScript 教程
jQuery 教程

jQuery 教程
CSS 教程

CSS 教程
PHP 教程

PHP 教程
Laravel 教程

Laravel 教程
TypeScript 教程

TypeScript 教程
WordPress 教程

WordPress 教程

数据库教程

SQL 教程

SQL 教程
SQLite 教程

SQLite 教程
MySQL 教程

MySQL 教程
PL/SQL 教程

PL/SQL 教程
MongoDB 教程

MongoDB 教程

图形图像教程

OpenCV 教程

OpenCV 教程

办公软件教程

Excel 教程

Excel 教程

Linux教程

Linux命令全集

Linux命令全集
Linux内核API

Linux内核API
LVGL 教程

LVGL 教程

计算机教程

操作系统 教程

操作系统 教程
计算机网络 教程

计算机网络 教程
C语言 教程

C语言 教程
C++ 教程

C++ 教程
Swift 教程

Swift 教程

大数据教程

Hadoop 教程

Hadoop 教程
Spark 教程

Spark 教程
Scala 教程

Scala 教程

开发工具教程

Git 教程

Git 教程
Jenkins 教程

Jenkins 教程
ChatGPT 教程

ChatGPT 教程
IntelliJ 教程

IntelliJ 教程

C++ 精选教程