检查是否可以对二进制字符串进行分区，使每个分区为5的幂

Question

我最近遇到了这个问题--给定一个二进制字符串，检查我们是否可以将字符串分割成0..n个部分，使每个部分都是5的次方。返回拆分的最小数目，如果可以的话。

例如：

input = "101101" - returns 1, as the string can be split once to form "101" and "101",as 101= 5^1.
input = "1111101" - returns 0, as the string itself is 5^3.
input = "100"- returns -1, as it can't be split into power(s) of 5.

我想出了这个递归算法：

1. 检查字符串本身是否为5的幂。如果是，则返回0
2. 否则，逐个字符迭代字符串，在每个点检查到目前为止看到的数字是否是5的幂。如果是，将1添加到split count，并从步骤1开始递归检查字符串的其余部分是否为5的幂。
3. 返回到目前为止看到的最小拆分数。

我在Java实施了上述algo。我相信它工作正常，但它是一个简单的递归解决方案。是否可以使用动态编程来改善运行时间？

代码如下：

public int partition(String inp){
    if(inp==null || inp.length()==0)
        return 0;
    return partition(inp,inp.length(),0);
}
public int partition(String inp,int len,int index){
    if(len==index)
        return 0;
    if(isPowerOfFive(inp,index))
        return 0;
    long sub=0;
    int count = Integer.MAX_VALUE;
    for(int i=index;i<len;++i){
        sub = sub*2 +(inp.charAt(i)-'0');
        if(isPowerOfFive(sub))
            count = Math.min(count,1+partition(inp,len,i+1));
    }
    return count;
}

帮助程序函数：

public boolean isPowerOfFive(String inp,int index){
    long sub = 0;
    for(int i=index;i<inp.length();++i){
        sub = sub*2 +(inp.charAt(i)-'0');
    }
    return isPowerOfFive(sub);
}

public boolean isPowerOfFive(long val){
    if(val==0)
        return true;
    if(val==1)
        return false;
    while(val>1){
        if(val%5 != 0)
            return false;
        val = val/5;
    }
    return true;
}

Answer 1

不是计算所有可能的子字符串，您可以检查5的幂的二进制表示，以搜索一个公共模式。使用类似于：

bc <<< "obase=2; for(i = 1; i < 40; i++) 5^i"

你得到：

5¹=101²=11001²
5⁴=1001110001_{2
5⁵=1100001101012
5⁶=111101000010012
5⁷=1001101001011012UB>
...
5²⁹=101000011000111100011111010111001101010111001000010111110010101010102}

如您所见，5的奇数次幂总是以101结尾，5的偶数次幂总是以模式10+1结尾（其中+表示一次或多次出现）。

您可以将输入字符串放入一个trie中，然后对其进行迭代，识别10+1模式，一旦匹配，就对其进行计算，检查是否为假阳性。

Answer 2

以下是可以做的简单改进：

• 在开始之前计算5的所有幂，这样可以更快地进行检查。
• 如果拆分次数已大于您已完成的最佳拆分次数，则停止拆分输入字符串。

下面是我使用这些想法的解决方案：

public static List<String> powers = new ArrayList<String>();
public static int bestSplit = Integer.MAX_VALUE;

public static void main(String[] args) throws Exception {
    // input string (5^5, 5^1, 5^10)
    String inp = "110000110101101100101010000001011111001";
    // calc all powers of 5 that fits in given string
    for (int pow = 1; ; ++pow) {
        String powStr = Long.toBinaryString((long) Math.pow(5, pow));
        if (powStr.length() <= inp.length()) { // can be fit in input string
            powers.add(powStr);
        } else {
            break;
        }
    }
    Collections.reverse(powers); // simple heuristics, sort powers in decreasing order
    // do simple recursive split
    split(inp, 0, -1);
    // print result
    if (bestSplit == Integer.MAX_VALUE) {
        System.out.println(-1);
    } else {
        System.out.println(bestSplit);
    }
}

public static void split(String inp, int start, int depth) {
    if (depth >= bestSplit) {
        return; // can't do better split
    }
    if (start == inp.length()) { // perfect split
        bestSplit = depth;
        return;
    }
    for (String pow : powers) {
        if (inp.startsWith(pow, start)) {
            split(inp, start + pow.length(), depth + 1);
        }
    }
}

我还发现了另一种看起来非常快的方法。

1. 计算字符串表示形式小于input字符串的5的所有幂。将这些字符串保存在powers数组中。
2. 对于来自powers数组的每个字符串power：如果power是input的子字符串，则将其start和end索引保存到edges数组（元组数组）中。
3. 现在我们只需要从edges数组中的边找到从索引0到索引input.length（）的最短路径。每个边具有相同的权重，因此使用BFS可以非常快地找到最短路径。
4. 找到的最短路径中的边数正是您所需要的--输入字符串的最小拆分数。