เราได้รับตัวเลขที่มีตัวเลขซ้ำหลายหลักเป็นสตริง เป้าหมายคือการหาจำนวนวิธีสะกดคำ ตัวอย่างเช่น 112233 สามารถสะกดเป็น double one, double two double 3 หรือ one two two 3 three
เราจะทำสิ่งนี้โดยการตรวจสอบตัวเลขอย่างต่อเนื่อง หากตัวเลขคือ "13" มีวิธีเดียวเท่านั้นที่จะสะกดเป็น "หนึ่งสาม" (20) หากตัวเลขเป็น “113” เท่ากับ “ดับเบิ้ลหนึ่งสาม”, “หนึ่งหนึ่งสาม” (21) วิธีการคือนับหนึ่งหลักต่อเนื่องในสตริงและคูณ 2(count-1) กับผลลัพธ์ก่อนหน้า
มาทำความเข้าใจกับตัวอย่างกัน
ป้อนข้อมูล
num=”11211”
ผลผลิต
Count of ways to spell a number with repeated digits are: 4
คำอธิบาย
ways are: 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
คำอธิบาย
ways are: 1. Two two one two 2. Double two one two
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้
-
เราใช้ string str แทนตัวเลข
-
ฟังก์ชัน word_spell(สตริง str) ใช้ตัวเลขใน str และส่งคืนวิธีการสะกดคำ
-
ใช้ตัวแปรเริ่มต้นนับเป็น 0 สำหรับวิธีดังกล่าว
-
ใช้สำหรับ loop traverse str สำหรับแต่ละหลัก
-
ใช้ตัวแปร temp เป็นจำนวนซ้ำของตัวเลขเฉพาะ ถ้า str[i]==str[i+1] ให้เพิ่มอุณหภูมิ
-
คำนวณ count=count*pow(2,temp-1)
-
เมื่อสิ้นสุดผลตอบแทนนับเป็นผลลัพธ์
ตัวอย่าง
#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
