# Decode Ways

Medium

## Question

A message containing letters from A-Z is being encoded to numbers using the following mapping:

``````'A' -> 1
'B' -> 2
...
'Z' -> 26
``````

Given an encoded message containing digits, determine the total number of ways to decode it.

Example
Given encoded message 12 , it could be decoded as AB (1 2) or L (12).
The number of ways decoding 12 is 2 .

## Thinking

DP

• State:
dp[i] how many ways to decode to i character
• Function:
dp[i] = 0 (if charAt(i - 1) is zero)
dp[i] = dp[i - 1] (if charAt(i - 1) is non-zero)
dp[i] = dp[i - 1] + dp [i - 2] if charAt(i - 1) + charAt (i - 2) between 10 and 26
• Initialize:
dp = 1
dp = 1
if s == null or s == “” or s startsWith “0” return 0.
dp[n]

Pay more attention about “0”. I was confused by it.

## Solution:

#### Java

``````public class Solution {
public int numDecodings(String s) {
if (s == null || s.equals("") || s.startsWith("0")) {
return 0;
}
int dp1 = 1;
int dp2 = 1;
int ways  = 1;
for (int i = 2; i <= s.length(); i++) {
int pre = s.charAt(i - 1) - '0';
int pre2 = s.charAt(i - 2) - '0';
int value = pre + pre2 * 10;
if (pre == 0) {
ways = 0;
}
if (value >= 10 && value <= 26) {
ways = ways + dp2;
}
dp2 = dp1;
dp1 = ways;
}
return ways;
}
}
``````