Count Combinations in the given String using Dynamic programming

user_19316252 0
Viewed 122

I found an exercise in the "Algorithms and Data Structures" book that I'm unable to solve.

Starting with a table of characters encoding:

| left | center |
|:---- |:-------|
| A    | 0      |
| B    | 00     |
| C    | 001    |
| D    | 010    |
| E    | 0010   |
| F    | 0100   |
| G    | 0110   |
| H    | 0001   |

This means that starting by a given string S = 00100, there are 5 possible sequences that can be decoded: ADA, AF, CAA, CB or EA.

Obviously not all strings can be decoded (e.g. 1111).

Write a program (in Java) that calculates the number of sequences that can encode S through dynamic programming.

Another example: the string 000100100010010000100100001001100 has 5567 possible sequences.

Hint: the subproblems are the prefixes of S

My attempt:

/**
 * this is the main part of the algorithm. I feel like this is way too slow
 * and it doesn't use dynamic programming.
 * 'encodings' is just an ArrayList with the specified values (e.g 00).
 */
private void count(String str) {
  for (String c : encodings) {
    if (str.length() > c.length()) {
      String subStringCodLength = str.substring(0, c.length());
      if (subStringCodLength.equals(c)) {
        String substring = str.substring(c.length());
        count(substring);
      }
    } else if (str.length() == c.length()) {
      if (encodings.contains(str)) {
        this.numOfDecodings++;
        break;
      }
    }
  }
}
dynamic-programming encoding algorithm java string
1 Answers

There are two approaches in Dynamic programming: Memoization and Tabulation.

Both are based and storing and reusing previously calculated results of subproblems. And as the hint says, divide the problem into subproblems based on the prefixes of the given string.

Memoization

Memoization technic is used together with recursion. A good choice of a mean for storing the intermediate results would be a Map.

When implementing a recursion, we need to describe two situations:

  • Base case - that represents a simple edge-case (or a set of edge-cases) for which the outcome is known in advance. For this problem, such edge-cases are:

    • the given string is empty and result would be 1 (an empty binary string "" results into an empty string of letters ""),
    • another case is when it's impossible to decode a given binary string and the result will be 0 (in the solution below it resolves naturally when the recursive case is being executed),
    • result for the given string has been already calculated and contained in the map.

  • Recursive case - a part of a solution where recursive calls a made and when the main logic resides. In the recursive case, we need to find each binary "binary letter" at the beginning of the string and then call the method recursively by passing the substring (without the "letter") as an argument. Results of these recursive calls need to be accumulated, stored in the map, and then provided as a return value.

That how it might look like:

public static int count(String str, List<String> letters, Map<String, Integer> vocab) {
    if (str.isEmpty()) { // base case - a combination was found
        return 1;
    }
    if (vocab.containsKey(str)) { // result was already computed and present in the map 
        return vocab.get(str);
    }

    int count = 0;

    for (String letter: letters) {
        if (str.startsWith(letter)) {
            count += count(str.substring(letter.length()), letters, vocab);
        }
    }
    vocab.put(str, count); // storing the total `count` into the map

    return count;
}

Tabulation

Tabulation technic isn't based on recursion, instead it utilizes loops.

Which makes this approach more reliable, because recursion has some limitation, especially in Java. Tabulation allows processing a massive input that can produce StackOverflowErrorwith Memoization.

Usually, arrays are used to store intermediate results while implementing a Tabulation.

To solve this problem, we need to create an array with the length of the given string + 1. Each element of the array will represent the number of ways to contract the substring from index 0 up to the index of the current element using a set of "binary letters". The final result will be stored at the last position of the array.

To initialize the array, we need to set a value of 1 to each element of the array that corresponds "binary letter" which happens to be a prefix of the given string. It's done in the populate() method. Then we need to iterate over array searching for the possible combinations that can be contacted based on the combinations that has been already found (i.e. based on the array elements that are not 0).

public static int count(String str, List<String> letters) {
    int[] tab = new int[str.length() + 1];
    
    populate(str,  letters,  tab);
    
    for (int i = 1; i < tab.length; i++) {
        if (tab[i] == 0) continue;
        for (String letter: letters) {
            if (i + letter.length() >= tab.length) continue;
            
            if (str.substring(i, i + letter.length()).equals(letter)) {
                tab[i + letter.length()] += tab[i];
            }
        }
    }
    return tab[tab.length - 1];
}

public static void populate(String str, List<String> letters, int[] tab) {

    for (String letter: letters) {
        if (letter.length() >= tab.length) continue;
    
        if (str.startsWith(letter)) {
            tab[letter.length()] += 1;
        }
    }
}

Demo

main()

public static void main(String[] args) {
    
    List<String> letters = List.of("0", "00", "001", "010", "0010", "0100", "0110", "0001"); // binary letters

    System.out.println(count("000100100010010000100100001001100", letters, new HashMap<>())); // Memoization
    System.out.println(count("000100100010010000100100001001100", letters)); // Tabulation
}

Output:

5567   // Memoization
5567   // Tabulation

A link to Online Demo

user_179499450
Related