จำนวนสตริงที่อักขระที่อยู่ติดกันมีความแตกต่างหนึ่งใน 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”...............

สำหรับความยาว =น.

สตริงที่ขึ้นต้นด้วย a=จำนวนสตริงที่มีความยาว n-1 เริ่มต้นด้วย b

สตริงที่ขึ้นต้นด้วย b=จำนวนสตริงที่มีความยาว n-1 เริ่มต้นด้วย a หรือ c

สตริงที่ขึ้นต้นด้วย c=ways จำนวนสตริงที่มีความยาว n-1 เริ่มต้นด้วย b หรือ d

เราจะแก้ปัญหานี้โดยใช้โปรแกรมไดนามิก

ใช้อาร์เรย์ arr[num+1][27] มีจำนวนสตริงของความยาว i เริ่มต้นด้วยตัวอักษร j ใน arr[i][j] arr[1][j] ทั้งหมดจะเป็น 1 สำหรับสตริง “a”, “b”...”z”

พักสำหรับ 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];

ผลลัพธ์จะเป็นผลรวมของจำนวนแถวที่นับ

• รับอินพุตจำนวนเต็ม

• ฟังก์ชัน different_strings(int num) รับค่า num และส่งกลับจำนวนสตริงที่อักขระที่อยู่ติดกันมีความแตกต่างอย่างใดอย่างหนึ่ง

• นับเริ่มต้นเป็น 0

• เริ่มต้น arr[num + 1][27] ด้วย 0 ทั้งหมด

• เริ่มต้น arr[1][0 ถึง 25] ด้วย 1 ทั้งหมด

• ข้ามอาร์เรย์ 2 มิติ arr[][] ใช้สองสำหรับการวนซ้ำจากแถวที่ 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