Chúng ta được cho một số chứa nhiều chữ số lặp lại dưới dạng một chuỗi. Mục đích là để tìm ra số cách đánh vần nó. Ví dụ:112233 có thể được đánh vần là đôi một, đôi hai đôi ba hoặc một một hai hai ba ba.
Chúng tôi sẽ làm điều này bằng cách kiểm tra các số liên tục. Nếu số là “13” thì chỉ có một cách để đánh vần nó là “một ba” (20). Nếu các chữ số là “113” thì cách “nhân đôi một ba”, “một một ba” (21). Vì vậy, cách tiếp cận là đếm một chữ số liên tục trong chuỗi và nhân 2 (đếm-1) với kết quả trước đó.
Hãy cùng hiểu với các ví dụ.
Đầu vào
num=”11211”
Đầu ra
Count of ways to spell a number with repeated digits are: 4
Giải thích
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
Đầu vào
num=”2212”
Đầu ra
Count of ways to spell a number with repeated digits are: 2
Giải thích
ways are: 1. Two two one two 2. Double two one two
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
-
Chúng tôi đang lấy chuỗi str để đại diện cho một số.
-
Hàm word_spell (chuỗi str) nhận số trong str và trả về cách đánh vần nó.
-
Lấy số lượng biến ban đầu là 0 cho những cách như vậy
-
Sử dụng vòng lặp for đi qua str cho từng chữ số.
-
Lấy nhiệt độ thay đổi làm số lần lặp lại của một chữ số cụ thể. Nếu str [i] ==str [i + 1], hãy tăng nhiệt độ.
-
Tính count =count * pow (2, temp-1)
-
Kết quả là cuối cùng trả về.
Ví dụ
#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;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Count of ways to spell a number with repeated digits are: 16