Data Structures & Algorithms in Java – Dynamic Programming – Decode Ways

Problem:

If A is encoded as 1 , B as 2 and so on until Z as 26 , then find the number of ways a given encoded string can be decoded.

For example:

The input “121”

can be decoded as 1, 2 ,1 (ABA) or 12 1(LA) or 1 21 (AU)

So the output is 3.

The input 11106 can be decoded as 1, 1, 10, 6 (AAJF) or 11, 10. 6 (KJF) .

It cannot be decoded as 1,1,1,06 because 06 is not valid only 6 is valid.

So the output is 2.

Try out the solution here:

https://leetcode.com/problems/decode-ways/

Solution:

Hint:

  • For every number find the number of ways the previous numbers can be decoded

Example:

Let’s take the example 226

For the first number 2 , the number of ways it can be decoded is just 1 representing B

For the second number 2 , the number of ways it can be decoded is 1 considering the single digit alone ( 2 representing B)

Considering the previous digit 2 , the number of ways it can be decoded is 1 (22 representing the letter V)

So 22 can be represented in two ways :

BB

V

So the number of ways of decoding 22 is 2.

Now let’s consider the next digit from 226 which is 6

The current input is 22 and we are going to add 6 again to it

For 22 there are two ways of decoding as already discussed : 2,2 and 22

If we add 6 again to the above it becomes 2,2,6 and 22,6 still the number of ways of decoding remains the same – 2 considering the single digit 6.

If we consider the previous digit along with the current digit then the combination becomes:

2 ,26 (BZ). The number of ways of decoding here is 1.

So considering both (single digit and double digit ) the number of ways of decoding is 3 (2+1)

So the total number of decoding ways is :

Number of ways a single digit can be decoded +

Number of ways the single digit along with the previous digit can be decoded

Also,

Number of ways a single digit can be decoded = Number of ways the string until the previous numbers to the single digit can be decoded (unless it is 0 which cannot be considered alone)

Number of ways a double digit can be decoded = Number of ways the string until the previous numbers to the double digit can be decoded

To implement the above solution you can either start from the first number and go till the end or start from the last number and go till the beginning.

Let’s find the recursive solution , starting from the last number and recursing till the beginning.

ALGORITHM:

STEP1: Declare a recursive function which takes the string as input and the starting index of the string

STEP2: In the recursive function write the base conditions:

If you reach the end of the string return 1 (The number of ways the last number alone can be decoded is 1)

If the number is 0 , then return 0 (0 cannot be considered as alone)

STEP3: Find the number of ways of decoding the next single number . This is the same as the number of ways of decoding the current number (considering we are starting from the end)

STEP4: If there are two more numbers from the current position , find the number of ways of decoding the next two numbers (if they are in the range of 11 to 26 – ignore single digits 01, 02,03 etc as they are already considered in STEP3)

STEP5: Add this to the value returned in STEP3 and return it.

In the above algorithm we follow the same logic:

Number of ways to decode a string at a particular position = Number of ways to decode the string until the previous position considering the single number at the current position + Number of ways to decode the string until the previous position considering the current number and the previous number together

The only change is we start from the end , so the logic becomes:

Number of ways to decode a string at a particular position = Number of ways to decode the string from the next position considering the single number at the current position +

Number of ways to decode to decode a string from the next position considering two numbers from the current position

Here is the code :

class Solution {
    public int numDecodings(String s) {
        
        
      
        return recursion(s,0);
        
        
    }
    
    
    public int recursion(String s,int start){
        
        
        
        if(start == s.length()) return 1;
        
        if(s.charAt(start) == '0') return 0;
        
        
        int value = recursion(s,start+1);
        
    
        
        if(start < s.length() - 1 ){
            
            
            Integer twoDigits = Integer.valueOf(s.substring(start,start+2));
            
            
            if(twoDigits >=10 && twoDigits <= 26){
                
                value += recursion(s,start+2);
            }
        }
        
        return value;
        
    }
}

The time complexity is exponential.

We can reduce same recursive calls by using Memoization ( storing the solution of sub problems) .

Here is the the same code as above with the only difference of storing the results of recursive calls in an array and returning the output of sub problems from the array if it is already present .

class Solution {
    public int numDecodings(String s) {
        
        int[] dp = new int[s.length()];
        Arrays.fill(dp,-1);
      
        return recursion(s,0,dp);
        
        
    }
    
    
    public int recursion(String s,int start,int[] dp){
        
        
        
        if(start == s.length()) return 1;
        
        if(s.charAt(start) == '0') return 0;
        
        
        if(dp[start] != -1){
            
            return dp[start];
            
        }
        
        int value = recursion(s,start+1,dp);
        
    
        
        if(start < s.length() - 1 ){
            
            
            Integer twoDigits = Integer.valueOf(s.substring(start,start+2));
            
            
            if(twoDigits >=10 && twoDigits <= 26){
                
                value += recursion(s,start+2,dp);
            }
        }
        
        
        dp[start] = value;
        return value;
        
    }
}

The time complexity now becomes O(n) and the extra space complexity is also O(n)

We can further avoid the recursive calls using dynamic programming as below. Here we store the results in an output array as we traverse from the end. The initial output is set to 1 and as we complete the iteration the final value gives the required output.

class Solution {
    public int numDecodings(String s) {
        int len = s.length();
        
        int[] dp = new int[len+1];
        
        dp[len] = 1;
        
        
        for(int i=len-1;i>=0;i--){
            
            
                     
            
            if( s.charAt(i) != '0'){
                
                dp[i] = dp[i+1];
            }
                
        if(i < len-1){
            Integer twoDigits = Integer.valueOf(s.substring(i,i+2));
            
            if(twoDigits >=10 && twoDigits <=26){
                
                dp[i] += dp[i+2];
            }
            
        }
            
            }
        
    
        
        return dp[0];
        
    }
}

We can also start from the beginning of the input instead of the end as below:

class Solution {
    public int numDecodings(String s) {
        
        
        int[] dp = new int[s.length()+1];
        
        
        dp[0] = 1;
        
        dp[1] = s.charAt(0) == '0'?0:1;
        
        for(int i=2;i<=s.length();i++){
            
            
            String first = s.substring(i-1,i);
            
            String second = s.substring(i-2,i);
            
            int oneDigit = Integer.valueOf(first);
            
            int twoDigits = Integer.valueOf(second);
            
            if ( oneDigit >= 1 && oneDigit <=9 ){
                
                dp[i] += dp[i-1];
            }
            
            if(twoDigits >=10 && twoDigits <=26){
                
                dp[i] += dp[i-2];
            }
        }
        
        return dp[s.length()];
        
        
    }
}

That’s it!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s