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 };

Loading Disqus comments...
Table of Contents