ALPHANUMBER - Editorial

PROBLEM LINK:

Practice
Contest

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.

  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
{

    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();
	}
}