PROBLEM LINK:
Author: Ram Agrawal
Tester: Ram Agrawal
Editorialist: Ram Agrawal
DIFFICULTY:
EASY.
PREREQUISITES:
DP
PROBLEM:
Meena is playing with numbers. He wants to change a number to a word containing letters from A-Z using the following mappings:
'A' = 1
'B' = 2
'C' = 3
...
'Y' = 25
'Z' = 26
He wants to count a total number of different words he can make with a number.
It may be assumed that the input contains valid digits from 0 to 9 and If there are leading 0’s, extra trailing 0’s, and two or more consecutive 0’s then it is an invalid string. So you need to print 0 in that case.
as the answer can be large return the answer modulo 109109 + 7.
EXPLANATION:
his problem is recursive and can be broken into sub-problems. We start from the end of the given digit sequence. We initialize the total count of decodings as 0. We recur for two subproblems.
- If the last digit is non-zero, recur for the remaining (n-1) digits and add the result to the total count.
- If the last two digits form a valid character (or smaller than 27), recur for remaining (n-2) digits and add the result to the total count.
SOLUTIONS:
Setter's Solution
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
static class FastReader {
BufferedReader be;
StringTokenizer st;
public FastReader()
{
br = new BufferedReader(
new InputStreamReader(System.in));
}
String next()
{
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
}
catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() { return Integer.parseInt(next()); }
long nextLong() { return Long.parseLong(next()); }
double nextDouble()
{
return Double.parseDouble(next());
}
String nextLine()
{
String str = "";
try {
str = br.readLine();
}
catch (IOException e) {
e.printStackTrace();
}
return str;
}
}
static class OutputWriter {
private final PrintWriter writer;
public OutputWriter(OutputStream outputStream) {
writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
}
public OutputWriter(Writer writer) {
this.writer = new PrintWriter(writer);
}
public void print(int[] array) {
for (int i = 0; i < array.length; i++) {
if (i != 0) {
writer.print(' ');
}
writer.print(array[i]);
}
}
public void printLine(int[] array) {
print(array);
writer.println();
}
public void close() {
writer.close();
}
public void printLine(long i) {
writer.println(i);
}
public void printLine(int i) {
writer.println(i);
}
public void printLine(char c)
{
writer.println(c);
}
public void print(Object... objects) {
for (int i = 0; i < objects.length; i++) {
if (i != 0) {
writer.print(' ');
}
writer.print(objects[i]);
}
}
public void printLine(Object... objects) {
print(objects);
writer.println();
}
}
public static int CountWays(String str)
{
int n=str.length();
int[] a=new int[n];
a[0]=1;
if(str.charAt(0)=='0')return 0;
int mod=1000000007;
for(int i=1;i<n;i++){
if(str.charAt(i-1)=='0'&& str.charAt(i)=='0'){
return 0;
}
else if(str.charAt(i-1)=='0'){
a[i]=a[i-1];
}
else if(str.charAt(i)=='0'){
if(str.charAt(i-1)=='1' || str.charAt(i-1)=='2'){
a[i]=(i>=2?a[i-2]:1);
}
else {
return 0;
}
}
else{
int x=Integer.parseInt(str.substring(i-1,i+1));
if(x<=26){
a[i]=(a[i-1]+(i>=2?a[i-2]:1))%mod;
}
else{
a[i]=a[i-1];
}
}
}return a[n-1];
}
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
FastReader sc = new FastReader();
OutputWriter out = new OutputWriter(System.out);
int t=sc.nextInt();
while(t-->0){
String str=sc.nextLine();
out.printLine(CountWays(str));
}
out.close();
}
}