# 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 = 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;
9         memset(dp,0,sizeof(dp));
10         dp = 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 };``````