计算 Java 中给定二进制字符串的所有可能解码组合

Question

假设我们有一个二进制值字符串，其中某些部分可能对应于特定的字母，例如：

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

例如，如果我们假设字符串 "00100"，我们可以有 5 种不同的可能性：

ADA
AF
CAA
CB
EA

我必须使用动态规划提取准确的组合数。

但是我在子问题的表述和相应的解向量的构成上有困难。

我感谢任何正确算法公式的指示。

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

Answer 1

希望这对您有所帮助。想法是用这些值创建每个可能的字符串并检查 input 是否以该值开头。如果不是，则切换到另一个索引。

如果您准备好测试用例，您可以验证更多。我只测试了 2-3 个值。

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

在主要方法中

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

我的测试结果：

input : 00100
Final count 5 

input : 000
Final count 3

Answer 2

本质上，动态规划是一种增强的brute-force方法。

就像brute-force的情况一样，我们需要生成所有可能的结果。但是与普通的 brute-force 相反，问题应该被分成更小的子问题，每个子问题的先前计算结果应该被存储和重用。

由于您使用的是递归您需要应用 so-called Memoization 技术来存储和重用中间结果.在这种情况下，HashMap 将是存储结果的完美方式。

但在应用 memoization 之前，为了更好地理解它，从一个干净简单的 递归解决方案 开始是有意义的正常工作，然后才用 DP 增强它。

普通递归

每个递归实现都应该包含两部分：

基本案例 - 表示结果已知的简单 edge-case（或一组 edge-case）提前。对于此问题，有两个 edge-case：给定字符串的长度为 0，结果为 1（空二进制字符串 "" 结果为空字符串字母 "")，另一种情况是无法解码给定的二进制字符串，结果将是 0（在下面的解决方案中，当 递归情况 正在执行）。
递归案例 - 解决方案的一部分，其中递归调用已完成并且主要逻辑所在。在递归情况下，我们需要在字符串的开头找到每个二进制“二进制字母”，然后通过传递子字符串（不带“字母”）递归调用该方法。这些递归调用的结果需要累加到方法返回的总计数中。

为了实现这个逻辑，我们只需要两个参数：要分析的二进制字符串和二进制字母列表:

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

这个简洁的解决方案已经能够产生正确的结果。现在，让我们通过应用 memoization.

将这个 brute-force 版本变成 DP-based 解决方案

动态规划

正如我之前所说，HashMap 将是存储中间结果的完美方式，因为允许将 count（组合数）与一个特定的字符串，然后几乎立即检索这个数字 (in O(1) time).

它可能看起来像：

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
}

输出：

5   // DP
5   // plain recursion

A link to Online Demo

计算 Java 中给定二进制字符串的所有可能解码组合

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

java

algorithm

recursion

memoization

dynamic-programming

普通递归

动态规划