# Decode Ways

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

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

Given a **non-empty** string containing only digits, determine the total number of ways to decode it.

**Example 1:**

```
Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).
```

**Example 2:**

```
Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
```

## Analysis

### **Dynamic Programming - 1**

`dp[i]`代表string s从0到i能够decode的数目, number of ways to decode string from 0 to i (included)

状态转移方程 `dp[i] = if (s.substring(i, i + 1) is valid decode) then dp[i - 1] else 0 + if (s.substring(i - 1, i + 1) is valid decode) then dp[i - 2] else 0`

### **Dynamic Programming - 2 (Preferred, more succinct, clear, no need of hashset)**

Ref: <https://leetcode.com/problems/decode-ways/discuss/30358/Java-clean-DP-solution-with-explanation>

Use 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.

### Dynamic Programming - 3

`dp[i]` - 从`0`到`i`个字符对应的decode ways。因此`dp[]`的size是`n`，而不是`n+1`。

和第二种方法类似，但是用charAt(i)来得到对应位置字符，运行效率更高：

```java
char ch = s.charAt(i);
int num = ch - '0';

int oneVal = 0;
if (num >= 1 && num <= 9) {
    oneVal = (i - 1 >= 0 ? dp[i - 1] : 1);
}

int twoVal = 0;
if (i > 0) {
    num += (s.charAt(i - 1) - '0') * 10;
    if (num >= 10 && num <= 26) {
        twoVal = (i - 2 >= 0 ? dp[i - 2] : 1);
    }
}

dp[i] = oneVal + twoVal;
```

并且可以用滚动数组优化空间复杂度为O(1)。

时间复杂度 O(n)。

## Solution

**Dynamic Programming - 1** - O(n) space O(n) time

```java
class Solution {
    public int numDecodings(String s) {
        if (s == null) return 0;
        Set<String> letters = new HashSet<String>();
        for (int i = 1; i <= 26; i++) {
            letters.add(Integer.toString(i));
        }
        int[] nums = new int[s.length()];
        nums[0] = letters.contains(s.substring(0, 1)) ? 1 : 0;
        if (s.length() == 1) return nums[0];
        nums[1] = (letters.contains(s.substring(1, 2)) ? nums[0] : 0) + 
                (letters.contains(s.substring(0, 2)) ? 1 : 0);
        for (int i = 2; i < s.length(); i++) {
            nums[i] = (letters.contains(s.substring(i, i + 1)) ? nums[i - 1] : 0) + 
                (letters.contains(s.substring(i - 1, i + 1)) ? nums[i - 2] : 0);
        }
        return nums[s.length() - 1];
    }
}
```

**Dynamic Programming - 2 - O(n) space, O(n) time**&#x20;

[substring 是 O(k) 时间复杂度](https://stackoverflow.com/questions/4679746/time-complexity-of-javas-substring)，其中k是substring长度。

```java
public class Solution {
    public int numDecodings(String s) {
        if(s == null || s.length() == 0) {
            return 0;
        }
        int n = s.length();
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = s.charAt(0) != '0' ? 1 : 0;
        for(int i = 2; i <= n; 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[n];
    }
}
```

### \***Dynamic Programming - 3 -** Reference - O(n) space, O(n) time

0 ms, faster than 100.00%

```java
/*
  v
226

num: 26
oneVal: 2
twoVal: 1
dp: 1 2 3

dp[i]=
dp[i-1]  1~9
+
dp[i-2]  10~26

dp[0]=1 1~9  1
dp[1]=dp[0]+(01~26) 2
dp[2]=dp[0]+dp[1] 3
*/

class Solution {  // O(N) | O(N)
    public int numDecodings(String s) {
        int n = s.length();
        if (n == 0) {
            return 0;
        }

        int[] dp = new int[n];

        for (int i = 0; i < n; ++i) {
            char ch = s.charAt(i);
            int num = ch - '0';

            int oneVal = 0;
            if (num >= 1 && num <= 9) {
                oneVal = (i - 1 >= 0 ? dp[i - 1] : 1);
            }

            int twoVal = 0;
            if (i > 0) {
                num += (s.charAt(i - 1) - '0') * 10;
                if (num >= 10 && num <= 26) {
                    twoVal = (i - 2 >= 0 ? dp[i - 2] : 1);
                }
            }

            dp[i] = oneVal + twoVal;
        }

        return dp[n - 1];
    }
}
```

### **Dynamic Programming - 3** - space optimized - O(1) space, O(n) time

```
/*
  v
226

num: 26
oneVal: 2
twoVal: 1
dp: 1 2 3

dp[i]=
dp[i-1]  1~9
+
dp[i-2]  10~26

dp[0]=1 1~9  1
dp[1]=dp[0]+(01~26) 2
dp[2]=dp[0]+dp[1] 3
*/
```

\-- 根据上一种方法，发现只需要dp\[0], dp\[1], dp\[2] 三个元素存储中间状态即可，因此可以用滚动数组优化空间。

Space: O(1)

Time: O(n)

Memory Usage: 33.5 MB, less than 89.69%

Runtime: 0 ms, faster than 100.00%

```java
class Solution { // O(1) space, O(n) time
    public int numDecodings(String s) {
        if (s == null || s.isEmpty()) {
            return 0;
        }
        int n = s.length();
        int[] dp = new int[3];

        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            int num = ch - '0';

            int oneDigit = 0;
            if (num >= 1 && num <= 9) {
                oneDigit = (i > 0) ? dp[(i - 1) % 3] : 1;
            }
            int twoDigits = 0;
            if (i > 0) {
                num += (s.charAt(i - 1) - '0') * 10;
                if (num >= 10 && num <= 26) {
                    twoDigits = (i > 1) ? dp[(i - 2) % 3] : 1;
                }
            }
            dp[i % 3] = oneDigit + twoDigits;
        }
        return dp[(n - 1) % 3];
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/dynamic_programming/decode-ways.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.