Count Possible Decoding of Given Sequence

1 = A
2 = B
.
.
.
26 = Z

Input : "121"
Output: 3
(possible combination ABA, AU, LA)

Input : "1234"
Output: 3
(possible combination ABCD, LCD, AWD)


package com.programming.other;

import java.util.Scanner;

class Test {

/**
* Time Complexity: O(N!)
* @param number
* @param length
* @return
*/
static int count_native(String number, int length) {
// base condition
if (length == 0 || length == 1) {
return 1;
}

// collect count
int count = 0;

// if last digit is not 0 and consider last digit in total count
if (number.charAt(length - 1) > '0') {
count = count_native(number, length - 1);
}

// if last 2 digits are more than or equals to 26 then consider last 2 digits
// also
if (number.charAt(length - 2) == '1'
|| (number.charAt(length - 2) == '2' && number.charAt(length - 1) <= '6')) {
count += count_native(number, length - 2);
}

return count;
}

/**
* Time Complexity: O(N)
* @param number
* @return
*/
static int count_optimized(String number) {
// base condition
if (number.length() == 0) {
return 0;
}
if (number.length() == 1) {
if (number.charAt(0) == '0') {
return 0;
} else {
return 1;
}
}

// store previous result
int[] previousResult = new int[number.length() + 1];
previousResult[0] = previousResult[1] = 1;

for (int i = 2; i <= number.length(); i++) {
// if last digit is not 0 and consider last digit in total count
if (number.charAt(i - 1) > '0') {
previousResult[i] += previousResult[i - 1];
}

// if last 2 digits are more than or equals to 26 then consider last 2 digits
// also
if (number.charAt(i - 2) == '1' || (number.charAt(i - 2) == '2' && number.charAt(i - 1) <= '6')) {
previousResult[i] += previousResult[i - 2];
}
}

return previousResult[number.length()];
}

public static void main(String args[]) {
// Scanner to read number
Scanner scan = new Scanner(System.in);

System.out.println("Enter number:");
String number = scan.next();

// close resource
scan.close();

// Print total count of strings
System.out.println(count_optimized(number));
}
}