Decode Ways

In this approach, we will generate all possible ways to decode the given input string. From every starting index of string we look at 1^st indexed character and if it is valid, that is it should be a non zero character and 1^st and 2^nd characters together and if it is valid, that is it should be within the boundaries of two digit possible letters 10-26 (J-Z).

Say for example if the input string is "1212", you can see that from 1^st digit '1' we can decode it to alphabet A or if you consider first two digits '12' we can decode it to L, similarly we will continue for other combinations of letters and decision tree for all possible combinations will look like below decision tree.

• We will create a function bruteForceApproach that takes input string s.
• Base cases are:
  • If the input string is null or starts with letter '0', then it is not possible to decode. So we will return 0.
  • If the input string length is 0 or 1, then there is a way to decode it, so return 1.
• Take the 1^st character of the string, since it is a valid letter. For the remainder of string call the function bruteForceApproach recursively.
• Then, check if we can take first two characters together and decode it, that means first two characters should be within the boundaries of 10-26. We can take them if one of below conditions are satisfied.
  • If the 1^st character is '1', meaning that we dont need to check for 2^nd character because the maximum value that can be at 2^nd character can be 9, so he possible values could be 10-19 and these are still within the boundaries of 10-26.
  • If the 1^st character is '2', then check for 2^nd character and consider it only if it is between '0' and '6' to ensure it is within boundaries of 20-26.
• If we are considering first two characters, then call the function bruteForceApproach recursively for remainder of the string and increment the count of possible decode ways.

public class DecodeWays {

    /* brute force approach solution */
    static int bruteForceApproach(String s) {
        if(s == null || s.startsWith("0")){
            return 0;
        }

        if(s.length() == 0 || s.length() ==1) {
            return 1;
        }

        String first_char_remainder = s.substring(1);
        int result = bruteForceApproach(first_char_remainder); // recursively call for remaining substring after 1st character
        char char_1 = s.charAt(0);
        char char_2 = s.charAt(1);
        if(char_1 == '1'
                || (char_1=='2' && (char_2=='0' || char_2 == '1' || char_2 =='2' || char_2 =='3'
                                    || char_2 == '4' || char_2 == '5' || char_2 == '6'))) {
            String second_char_remainder = s.substring(2);
            result+= bruteForceApproach(second_char_remainder);
        }
        return result;
    }

}

Complexity Analysis:

Time complexity: Above code runs in O(2ⁿ) time where n is the length of input string, this is because we are generating a decision tree with possible sub problems by taking possibilities with first character and first two characters.
Space complexity: O(n) since we calling the function recursively, this is the stack memory.

From the above brute force approach, we can notice that there are some overlapping problems, such as sub problem with node 12 on the left side and the sub problem with node 12 on the right side are same. So, we could cache the results of sub problem and re-use that.

• If we look at the decision tree diagram from above brute force aproach, highlighted sub problems are overlapping.
• So, in this approach, we will be caching sub problem result into a HashMap with input string s as key and its result as value. When a sub problem is repeated and found in cache, we will return it, otherwise we will call the function recursively and cache its result.

import java.util.HashMap;

public class DecodeWays {

    /* DP memoize solution */
    static int dpMemoizeApproach(String s) {
        HashMap<String, Integer> cache = new HashMap<>();
        return dpMemoizeApproachRec(s, cache);
    }
    static int dpMemoizeApproachRec(String s, HashMap<String, Integer> cache) {
        if(s == null || s.startsWith("0")){
            return 0;
        }

        if(s.length() == 0 || s.length() ==1) {
            return 1;
        }

        if(cache.containsKey(s)) { // re-use cached result if it exists
            return cache.get(s);
        }

        String first_char_remainder = s.substring(1);
        int result = bruteForceApproach(first_char_remainder); // recursively call for remaining substring after 1st character
        char char_1 = s.charAt(0);
        char char_2 = s.charAt(1);
        if(char_1 == '1'
                || (char_1=='2' && (char_2=='0' || char_2 == '1' || char_2 =='2' || char_2 =='3'
                                    || char_2 == '4' || char_2 == '5' || char_2 == '6'))) {
            String second_char_remainder = s.substring(2);
            result+= bruteForceApproach(second_char_remainder);
        }
        cache.put(s, result); // cache result
        return result;
    }

}

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the length of input string s.
Space complexity: O(n) for the cache we are maintaining and stack for recursive calls.

In this approach we will look at solving the problem using Dynamic programming using tabulation caching mechanism.
The time and memory complexity will be same as above solution using memoization, but we can notice a pattern to improve memory complexity to constant in later solution.

In this solution, we are going to create a temporary array to cache the possible ways to decode at current index, and for the next subsequent index possibilities, use the cache built so far and continue exploring number of ways to decode. The main intution in this solution is:

• When we are at index i, if that element is 1 or above, then consider it as a possibility as the value will be between 1-9 and update the cache at current index cache[i] with previous value cache[i-1] from cache.
  The reason why we do this is because when decoding is possible at current index element, then we need to update the cache at current index to indicate that decoding can continued to current index.
  Java

  cache[i] += cache[i-1];

• Now, we also need to check whether decoding with two digits is possible or not. i.e. with previous element and current element. If the previous value is 1 or if previous value is 2 and current value is between 0-6, then there is a possibility to decode using two digits at current index. So, we will update the cache at current index by adding cache value from i-2 index.
Java

cache[i] += cache[i-2];

Consider an example with input string "1212":

public class DecodeWays {

  /* DP tabulation approach */
  static int dpTabulationApproach(String s) {
      if(s.charAt(0) == '0') {
          return 0;
      }
      int[] count = new int[s.length()+1];
      count[0] = 1; // dummy value
      count[1] = 1; //decode possibilities for 0th index element from input string
      for(int i=2; i<=s.length(); i++) {

          int current = s.charAt(i-1); // though we are at i=2, we have to continue from 1st index of input string
          int prev = s.charAt(i-2);

          if(current > '0'){ // It does ascii comparison, but this is fine as ASCII values for 1 -9 will be greater than ASCII of 0
              count[i] += count[i-1];
          }
          if(prev =='1' ||
                  (prev == '2' && (current =='0' || current == '1' || current == '2' || current == '3'
                                  || current == '4' || current =='5' || current =='6'))) {
              count[i] += count[i-2];
          }
      }
      // finally take the last element of DP tabulation array
      return count[s.length()];
  }

}

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the length of input string s.
Space complexity: O(n) for the cache we are maintaining.

If you observe above solution DP using tabulation we are maintaining a temporary array with size n+1 size to cache the results, but when we are at index i we only need previous two values from the cache. So, in this approach we are going to make a small change to above program to keep track of only two previous values of cache and avoid temporary array that we have created.

public class DecodeWays {

  /* DP memory optimized */
  static int doMemoryOptimized(String s) {
      if(s.charAt(0) == '0') {
          return 0;
      }
      int prev = 1;
      int current = 1;
      for(int i=2; i<=s.length(); i++) {

          int one_char = s.charAt(i-1);
          int two_char = s.charAt(i-2);

          int temp = 0;
          if(one_char > '0'){
              temp += current;
          }
          if(two_char =='1' ||
                  (two_char == '2' && (one_char =='0' || one_char == '1' || one_char == '2' || one_char == '3'
                          || one_char == '4' || one_char =='5' || one_char =='6'))) {
              temp += prev;
          }
          prev = current;
          current = temp;
      }
      // finally return current value
      return current;
  }

}

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the length of input string s.
Space complexity: O(1) since we are maintaining previous two values.