เราได้รับตัวเลขที่มีตัวเลขซ้ำมากเป็นสตริง เป้าหมายคือหาจำนวนวิธีในการสะกดมัน ตัวอย่าง 112233 สามารถสะกดได้เป็น "double one, double two double three" หรือ "one one two two three three"
เราจะทำได้โดยการตรวจสอบตัวเลขที่ติดกัน ถ้าตัวเลขคือ "13" มีเพียงหนึ่งวิธีสะกดคือ "one three" (20) ถ้าตัวเลขคือ "113" วิธีคือ "double one three", "one one three" (21) ดังนั้นวิธีการคือนับตัวเลขที่ติดกันในสตริงและคูณ 2^(count-1) กับผลลัพธ์ก่อนหน้า
มาทำความเข้าใจด้วยตัวอย่าง
อินพุต
num="11211"
เอาต์พุต
Count of ways to spell a number with repeated digits are: 4
คำอธิบาย
วิธีคือ: 1. One one two one one 2. Double one two one one 3. One one two double one 4. Double one two double one
อินพุต
num="2212"
เอาต์พุต
Count of ways to spell a number with repeated digits are: 2
คำอธิบาย
วิธีคือ: 1. Two two one two 2. Double two one two
วิธีการที่ใช้ในโปรแกรมด้านล่าง
เราใช้สตริง str เพื่อแทนตัวเลข
ฟังก์ชัน word_spell(string str) รับตัวเลขใน str และคืนค่าวิธีการสะกด
ใช้ตัวแปร count เริ่มต้นเป็น 0 สำหรับวิธีการดังกล่าว
ใช้ลูป for ท่อง str สำหรับแต่ละตัวเลข
ใช้ตัวแปร temp เป็นจำนวนการซ้ำของตัวเลขเฉพาะ ถ้า str[i]==str[i+1] เพิ่ม temp
คำนวณ count=count*pow(2,temp-1)
ในที่สุดคืนค่า count เป็นผลลัพธ์
ตัวอย่าง
#include<bits/stdc++.h> using namespace std; long long int word_spell(string str){ long long int count = 1; int len = str.length(); for (int i=0; i<len; i++){ int temp = 1; while(i < len-1 && str[i+1] == str[i]){ temp++; i++; } count = count * pow(2, temp-1); } return count; } int main(){ string str = "222211"; cout<<"Count of ways to spell a number with repeated digits are: "<<word_spell(str); return 0; }เอาต์พุต
ถ้าเรารันโค้ดด้านบนจะได้ผลลัพธ์ดังนี้ −
Count of ways to spell a number with repeated digits are: 16
