计算给定二进制字符串在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

本质上，动态规划是一种增强的蛮力方法。

就像暴力破解一样，我们需要生成所有可能的结果。但是，与简单的暴力破解相反，问题应该被分成更小的子问题，并且每个子问题的先前计算结果应该被存储和重用。

由于使用递归，因此需要应用所谓的记忆技术，以便存储和重用中间结果。在这种情况下，HashMap将是存储结果的完美方法。

但是为了更好地理解，在应用记忆法之前，从一个干净简单的递归解开始是有意义的，它可以正确工作，然后用DP增强它。

普通递归每个递归实现应该包含两个部分:

• 基本情况-代表一个简单的边缘情况(或一组边缘情况)，其结果是预先知道的。对于这个问题，有两种边缘情况:给定字符串的长度为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;
}

这个简洁的解决方案已经能够产生正确的结果。现在，让我们通过应用备忘录，将这个暴力版本转变为基于dp的解决方案。

动态编程

如前所述，HashMap将是存储中间结果的完美方法，因为它允许将计数(组合数)与特定字符串关联，然后几乎立即检索该数字(O(1)中的)。

)。这就是它的样子:

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

在线演示的链接

Answer 2

希望这对你有帮助。想法是用这些值创建每个可能的字符串，并检查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;
}

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

我的测试结果:

input : 00100
Final count 5 
input : 000
Final count 3