C++에서 인접 문자의 차이가 1인 문자열 수

<시간/>

입력으로 숫자가 주어집니다. 목표는 모든 인접 문자의 ASCII 값 차이가 1이 되도록 길이가 num인 가능한 문자열의 수를 계산하는 것입니다.

num이 2이면 문자열은 "ab", "ba", "bc", "cb", ....."yz", "zy"가 됩니다.

예를 들어 이해하자

입력 - 숫자=3

출력 − 인접 문자의 차이가 1인 문자열의 개수는 − 98

설명 − 일부 샘플 문자열은 "abc", "aba", "cde" ....."xyx", "zyz", "xyz"입니다.

입력 - 숫자=2

출력 − 인접 문자의 차이가 1인 문자열의 개수는 − 50

설명 − 일부 샘플 문자열은 "ab", "ba", "cd" …..."xy", "zy", "yz"입니다.

아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.

길이 =2의 경우.

="ab"로 시작하는 문자열

b="ba", "bc"로 시작하는 문자열

c="cd", "cb"로 시작하는 문자열..............

길이 =n.

a로 시작하는 문자열 =b로 시작하는 길이가 n-1인 문자열의 수

b로 시작하는 문자열 =또는 c로 시작하는 길이가 n-1인 문자열의 수

c로 시작하는 문자열 =b 또는 d로 시작하는 길이가 n-1인 문자열의 수

동적 프로그래밍을 사용하여 이 문제를 해결할 것입니다.

배열 arr[num+1][27]을 가져옵니다. arr[i][j]에서 알파벳 숫자 j로 시작하는 길이 i의 여러 문자열을 포함합니다. 모든 arr[1][j]는 문자열 "a", "b"..."z"에 대해 1이 됩니다.

arr[2 ~ num+1][0 ~ 25]에 대해 휴식을 취하고 j=0에 대해 arr[i][j]=arr[i-1][j+1]을 설정합니다. 그렇지 않으면 설정 arr[i][j] =arr[i-1][j-1] + arr[i-1][j+1];

결과는 num번째 행 개수의 합계입니다.

정수 입력
함수 difference_strings(int num)는 num을 취하고 인접한 문자의 차이가 1인 문자열의 개수를 반환합니다.
초기 카운트를 0으로 합니다.
arr[num + 1][27]을 모두 0으로 초기화합니다.
arr[1][0 ~ 25]를 모두 1로 초기화합니다.
26개 알파벳 모두에 대해 2행에서 마지막 행까지 및 0에서 25열까지 2개의 for 루프를 사용하여 2D 배열 arr[][]를 탐색합니다.
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 to 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