Count all possible decoding Combination of the given binary String in Java-CodePudding

Suppose we have a string of binary values in which some portions may correspond to specific letters, for example:

A = 0
B = 00
C = 001
D = 010
E = 0010
F = 0100
G = 0110
H = 0001

For example, if we assume the string "00100", we can have 5 different possibilities:

ADA
AF
CAA
CB
EA

I have to extract the exact number of combinations using Dynamic programming.

But I have difficulty in the formulation of subproblems and in the composition of the corresponding vector of solutions.

I appreciate any indications of the correct algorithm formulation.

class countString {

    static int count(String a, String b, int m, int n) {

        if ((m == 0 && n == 0) || n == 0)
            return 1;

        if (m == 0)
            return 0;

        if (a.charAt(m - 1) == b.charAt(n - 1))
            return count(a, b, m - 1, n - 1)  
                   count(a, b, m - 1, n);
        else
            return count(a, b, m - 1, n);
    }

    public static void main(String[] args) {
        Locale.setDefault(Locale.US);
        ArrayList<String> substrings = new ArrayList<>();
        substrings.add("0");
        substrings.add("00");
        substrings.add("001");
        substrings.add("010");
        substrings.add("0010");
        substrings.add("0100");
        substrings.add("0110");
        substrings.add("0001");

        if (args.length != 1) {
            System.err.println("ERROR - execute with: java countString -filename- ");
            System.exit(1);
        }

        try {
            Scanner scan = new Scanner(new File(args[0])); // not important
            String S = "00100";

            int count = 0;

            for(int i=0; i<substrings.size(); i  ){
                count = count   count(S,substrings.get(i),S.length(),substrings.get(i).length());
            }

            System.out.println(count);

        } catch (FileNotFoundException e) {
            System.out.println("File not found "   e);
        }
    }
}

CodePudding user response：

In essence, Dynamic Programming is an enhanced brute-force approach.

Like in the case of brute-force, we need to generate all possible results. But contrary to a plain brute-force the problem should be divided into smaller subproblems, and previously computed result of each subproblem should be stored and reused.

Since you are using recursion you need to apply so-called Memoization technic in order to store and reuse the intermediate results. In this case, HashMap would be a perfect mean of storing results.

But before applying the memoization in order to understand it better, it makes sense to start with a clean and simple recursive solution that works correctly, and only then enhance it with DP.

Plain Recursion

Every recursive implementation should contain two parts:

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, there are two edge-cases: the length of the given string is 0 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 result will be 0 (in the solution below it resolves naturally when the recursive case is being executed).
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"). Results of these recursive calls need to be accumulated in the total count that will returned from the method.

In order to implement this logic we need only two arguments: the binary string to analyze and a list of binary letters:

public static int count(String str, List<String> letters) {
    if (str.isEmpty()) { // base case - a combination was found
        return 1;
    }

    // recursive case
    int count = 0;
    
    for (String letter: letters) {
        if (str.startsWith(letter)) {
            count  = count(str.substring(letter.length()), letters);
        }
    }        
    return count;
}

This concise solution is already capable of producing the correct result. Now let's this brute-force into a DP-based solution, by applying the memoization.

Dynamic Programming

As I've told, a HashMap will be a perfect mean to store the intermediate results because allows to associate a count (number of combinations) with a particular string and then retrieve this number almost instantly (in O(1) time).

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

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("00100", letters, new HashMap<>())); // DP
    System.out.println(count("00100", letters));                  // brute-force recursion
}

Output:

5   // DP
5   // plain recursion

A link to Online Demo

CodePudding user response：

Hope this helps. Idea is to create every possible string with these values and check whether input starts with the value or not. If not then switch to another index.

If you have test cases ready with you you can verify more. I have tested only with 2-3 values.

public int getCombo(String[] array, int startingIndex, String val, String input) {
    int count = 0;
    for (int i = startingIndex; i < array.length; i  ) {
        String matchValue = val   array[i]; 

        if (matchValue.length() <= input.length()) {
            // if value matches then count   1
            if (matchValue.equals(input)) {
                count  ;
                System.out.println("match Found---->"   count); //ommit this sysout , its only for testing.
                return count;
            } else if (input.startsWith(matchValue)) { // checking  whether the input is starting with the new value 
                // search further combos
                count  = getCombo(array, 0, matchValue, input);
            }
        }
    }
    return count;
}

In main Method

String[] arr = substrings.toArray(new String[0]);
int count = 0;
for (int i = 0; i < arr.length; i  ) {
    System.out.println("index----?> "   i);
   
    //adding this condition for single  inputs i.e "0","010";
    if(arr[i].equals(input))
         count  ;
    else 
        count = count   getCombo(arr, 0, arr[i], input);
}

System.out.println("Final count :  "   count);

My test results :

input : 00100
Final count 5 

input : 000
Final count 3