# decode ways

## decode ways

### Asked this problem in fb's interview

I was asked to resolve this problem in fb's phone interview. This problem is not so hard. It is a dynamic program problem.`dp[i]`

could be transformed from `dp[i-1]`

and `dp[i-2]`

if the substring of them is valid.

### Space complexity O(n)

```
1 class Solution {
2 public:
3 int numDecodings(string s) {
4 int l = s.length();
5 if ( l == 0 ) {
6 return 0;
7 }
8 int dp[l+1];
9 memset(dp,0,sizeof(dp));
10 dp[0] = 1;
11 for ( int i = 1; i <= l; i++ ) {
12 int now = s[i-1]-'0';
13 if ( now != 0 ) {
14 dp[i] += dp[i-1];
15 }
16 if ( i > 1 ) {
17 int bef = s[i-2]-'0';
18 bef = bef*10+now;
19 if ( bef != now && bef >= 1 && bef <= 26 ) {
20 dp[i] += dp[i-2];
21 }
22 }
23 }
24 return dp[l];
25 }
26 };
```

### Const space solution

After giving out that solution. I was asked to improve it to save the space complexity.
I found when we get `dp[i]`

, things before `dp[i-1]`

is no more used. **Do not forget to set dp[i%3] to zero at the begin of each loop iteration.**

```
1 class Solution {
2 public:
3 int numDecodings(string s) {
4 int l = s.length();
5 if ( l == 0 ) {
6 return 0;
7 }
8 int dp[3];
9 memset(dp,0,sizeof(dp));
10 dp[0] = 1;
11 for ( int i = 1; i <= l; i++ ) {
12 int now = s[i-1]-'0';
13 dp[i%3] = 0;
14 if ( now != 0 ) {
15 dp[i%3] += dp[(i-1)%3];
16 }
17 if ( i > 1 ) {
18 int bef = s[i-2]-'0';
19 bef = bef*10+now;
20 if ( bef != now && bef >= 1 && bef <= 26 ) {
21 dp[i%3] += dp[(i-2)%3];
22 }
23 }
24 }
25 return dp[l%3];
26 }
27 };
```