จำนวนสตริงที่ตัวอักษรติดกันมีความต่าง 1 ใน C++

เราได้รับตัวเลข num เป็นอินพุต เป้าหมายคือนับจำนวนสตริงที่เป็นไปได้ของความยาว num โดยที่ตัวอักษรติดกันทั้งหมดมีความต่างของค่า ASCII เป็น 1

ถ้า num เป็น 2 สตริงจะเป็น "ab", "ba", "bc", "cb", … "yz", "zy"

ตัวอย่าง

อินพุต - num=3

เอาต์พุต - จำนวนสตริงที่ตัวอักษรติดกันมีความต่าง 1 คือ - 98

คำอธิบาย - ตัวอย่างสตริงบางส่วน: "abc", "aba", "cde" … "xyx", "zyz", "xyz"

อินพุต - num=2

เอาต์พุต - จำนวนสตริงที่ตัวอักษรติดกันมีความต่าง 1 คือ - 50

คำอธิบาย - ตัวอย่างสตริงบางส่วน: "ab", "ba", "cd" … "xy", "zy", "yz"

แนวทางที่ใช้ในโปรแกรมด้านล่าง

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

สตริงเริ่มต้นด้วย a = "ab"

สตริงเริ่มต้นด้วย b = "ba", "bc"

สตริงเริ่มต้นด้วย c = "cd", "cb" …

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

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

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

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

เราจะแก้ปัญหานี้โดยใช้ Dynamic Programming

สร้างอาร์เรย์ 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]

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

• รับค่าจำนวนเต็ม num
• ฟังก์ชัน difference_strings(int num) รับ num และคืนค่าจำนวนสตริงที่ตัวอักษรติดกันมีความต่าง 1
• ตั้งค่า count เริ่มต้นเป็น 0
• เริ่มต้น arr[num + 1][27] ด้วย 0 ทั้งหมด
• เริ่มต้น arr[1][0 ถึง 25] ด้วย 1 ทั้งหมด
• เดินทางผ่านอาร์เรย์ 2 มิติ 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] เข้า count
• คืนค่า count เป็นผลลัพธ์

ตัวอย่างโค้ด

#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