 ALPHANUMBER - Editorial

Author: Ram Agrawal
Tester: Ram Agrawal
Editorialist: Ram Agrawal

EASY.

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.

1. If the last digit is non-zero, recur for the remaining (n-1) digits and add the result to the total count.
2. 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
{

StringTokenizer st;

{
}

String next()
{
while (st == null || !st.hasMoreElements()) {
try {
}
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 {
}
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=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
{