C ++中相邻字符相差一的字符串计数
给我们一个数字作为输入。目的是计算长度为num的可能字符串的数量,以使所有相邻字符的ascii值之间的差为1。
如果num为2,则字符串将为“ab”,“ba”,“bc”,“cb”,……..“yz”,“zy”。
让我们用例子来理解
输入-num=3
输出-相邻字符相差一的字符串数为-98
说明-一些示例字符串是:“abc”,“aba”,“cde”.....“xyx”,“zyz”,“xyz”。
输入-num=2
输出-相邻字符相差一的字符串数为-50
说明-一些示例字符串是:“ab”,“ba”,“cd”.....“xy”,“zy”,“yz”。
以下程序中使用的方法如下
对于长度=2。
以a=“ab”开头的字符串
以b=“ba”,“bc”开头的字符串
以c=“cd”,“cb”开头的字符串......
对于长度=n。
以a开头的字符串=以b开头的长度为n-1的字符串数的方式
以b开头的字符串=以a或c开头的长度为n-1的字符串的数量
以c开头的字符串=以b或d开头的长度为n-1的字符串数的方式
我们将使用动态编程解决此问题。
取一个数组arr[num+1][27]。包含许多长度为i的字符串,这些字符串以arr[i][j]中的字母数字j开头。对于字符串“a”,“b”...“z”,所有arr[1][j]均为1。
对于arr[2到num+1][0到25]休息,将arr[i][j]=arr[i-1][j+1]设为j=0。其他集arr[i][j]=arr[i-1][j-1]+arr[i-1][j+1];
结果将是第num行计数的总和。
取输入整数num
函数difference_strings(intnum)获取num并返回相邻字符之间的差异为一的字符串的计数
将初始计数设为0。
用全0初始化arr[num+1][27]。
用全1初始化arr[1][0至25]。
遍历2D数组arr[][],使用两个for循环从第2行到最后一行,并使用0到25列表示所有26个字母。
对于j=0,起始字符为'a'。将当前计数设置为arr[i][j]=arr[i-1][j+1];
否则设置arr[i][j]=(arr[i-1][j-1]+arr[i-1][j+1])
现在,在上述循环结束之后,遍历最后一行并添加arr[num][0至25]进行计数。
返回计数作为结果。
示例
#include <bits/stdc++.h> using namespace std; int difference_strings(int num){ long int count = 0; long int arr[num + 1][27]; memset(arr, 0, sizeof(arr)); for (int i = 0; i <= 25; i++){ arr[1][i] = 1; } for (int i = 2; i <= num; i++){ for (int j = 0; j <= 25; j++){ if (j == 0){ arr[i][j] = arr[i - 1][j + 1]; } else{ arr[i][j] = (arr[i - 1][j - 1] + arr[i - 1][j + 1]); } } } for (int i = 0; i <= 25; i++){ count = (count + arr[num][i]); } return count; } int main(){ int num = 2; cout<<"Count of strings where adjacent characters are of difference one are: "<<difference_strings(num); return 0; }
输出结果
如果我们运行上面的代码,它将生成以下输出-
Count of strings where adjacent characters are of difference one are: 50