BiruLyu
8/2/2017 - 9:00 PM

## 91. Decode Ways(#).java

public class Solution {

int[] l;

public int numDecodings(String s) {

if (s == null || s.length() == 0) {
return 0;
}

//return helper(s);

return helper2(s);
//l = new int[s.length()+1];
//return helper3(s);
}

public int helper2(String s) {
if (s.charAt(0) == '0') return 0;

int n = s.length();
int[] count = new int[n+1]; // A table to store results of subproblems
count[0] = 1;
count[1] = 1;

for (int i = 2; i <= n; i++)
{
count[i] = 0;

// If the last digit is not 0, then last digit must add to
// the number of words
if (s.charAt(i-1) > '0')
count[i] = count[i-1];

// If second last digit is smaller than 2 and last digit is
// smaller than 7, then last two digits form a valid character
if (s.charAt(i-2) == '1' || (s.charAt(i-2) == '2' && s.charAt(i-1) < '7') )
count[i] += count[i-2];
}
return count[n];
}

public int helper(String s) {

if (s == null || s.length() == 0) {
return 1;
}

if (s.charAt(0) == '0') {
return 0;
}

if (s.length() == 1) {
return 1;
}

char a1 = s.charAt(0);
char a2 = s.charAt(1);
int count = 0;

count += helper(s.substring(1));

if (a1 == '1' || (a1 == '2' && a2 <= '6')) {
count += helper(s.substring(2));
}

return count;
}

public int helper3(String s) {

if (s == null || s.length() == 0) {
return 1;
}

if (s.charAt(0) == '0') {
return 0;
}

if (s.length() == 1) {
return 1;
}

if (l[s.length()] != 0) {
return l[s.length()];
}

char a1 = s.charAt(0);
char a2 = s.charAt(1);
int count = 0;

count += helper3(s.substring(1));

if (a1 == '1' || (a1 == '2' && a2 <= '6')) {
count += helper3(s.substring(2));
}

l[s.length()] = count;

return count;
}
}
/*
I used a dp array of size n + 1 to save subproblem solutions. dp[0] means an empty string will have one way to decode, dp[1] means the way to decode a string of size 1. I then check one digit and two digit combination and save the results along the way. In the end, dp[n] will be the end result.
*/
public class Solution {
public int numDecodings(String s) {
if (s == null || s.length() < 1) return 0;
int len = s.length();
int[] dp = new int[len + 1];
dp[0] = 1;
dp[1] = s.charAt(0) == '0' ? 0 : 1;
for (int i = 2; i <= len; i++) {
int first = Integer.valueOf(s.substring(i-1, i));
int second = Integer.valueOf(s.substring(i-2, i));
if(first >= 1 && first <= 9) {
dp[i] += dp[i-1];
}
if(second >= 10 && second <= 26) {
dp[i] += dp[i-2];
}
}
return dp[len];
}
}