检查二进制字符串是否可以分区，以使每个分区的乘方为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实现了上述算法。我相信它可以正常运行，但这是一个简单的递归解决方案。可以使用动态编程来改善运行时间吗？

代码如下：

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 的所有幂，这样您可以更快地进行检查。
• 如果分割数已经大于您已完成的最佳分割数，则停止分割输入字符串。

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

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