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

Question

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

示例为：

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.

我想出了这个递归算法：

检查字符串本身是否是5的幂，如果是，return 0
否则，一个字符一个字符地遍历字符串，在每个点检查目前看到的数字是否是 5 的幂。如果是，将 1 加到拆分计数中并递归地检查字符串的其余部分的幂5 从第 1 步开始。
return目前看到的最小分割数。

我在 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

您只需将给定字符串的值保存在地图中。例如，如果你有一个这样结尾的字符串：（每个字母可以是任意大小的字符串）

ABCD

你发现A mod 5部分没问题，所以你再试BCD，但发现B mod 5也可以，C和[=也一样16=] 和 CD 一起。现在您应该缓存了以下结果：

C -> 0
D -> 0
CD -> 0
BCD -> 1  # split B/CD is the best

但是你还没有完成 ABCD - 你发现 AB mod 5 没问题，所以你检查结果 CD - 它已经在缓存中而你没有必须从头处理。

实际上，您只需要缓存来自 partition() 的答案——无论是针对实际字符串还是针对 (string, start, length) 元组。哪一个更好取决于您有多少重复序列以及比较内容或仅比较索引是否更快。

Answer 2

您可以检查 5 次方的二进制表示以寻找通用模式，而不是计算所有可能的子串。使用类似的东西：

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

你得到：

5¹ = 101₂
5² = 11001₂
5³ = 1111101₂
5⁴ = 1001110001₂
5⁵ = 110000110101₂
5⁶ = 11110100001001₂
5⁷ = 10011000100101101₂
5⁸ = 1011111010111100001₂
5⁹ = 111011100110101100101₂
5¹⁰ = 100101010000001011111001₂
5¹¹ = 10111010010000111011011101₂
5¹² = 1110100011010100101001010001₂
5¹³ = 1001000110000100111001110010101₂
5¹⁴ = 101101011110011000100000111101001₂
5¹⁵ = 11100011010111111010100100110001101₂
5¹⁶ = 10001110000110111100100110111111000001₂
5¹⁷ = 1011000110100010101111000010111011000101₂
5¹⁸ = 110111100000101101101011001110100111011001₂
...
5²⁹ = 10100001100011110000011111010111001101101011100100001011111001010101₂

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

您可以将您的输入字符串放在一个特里树中，然后遍历它来识别 10+1 模式，一旦您找到匹配项，就对其进行评估以检查是否不是误报。

Answer 3

以下是可以完成的简单改进：

开始前先计算 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);
        }
    }
}

编辑：

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

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

Answer 4

下面给出了 C++ 中的解决方案。使用动态规划，我正在考虑所有可能的拆分并保存最佳结果。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int isPowerOfFive(ll n)
{
    if(n == 0) return 0;
    ll temp = (ll)(log(n)/log(5));
    ll t = round(pow(5,temp));
    if(t == n)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
ll solve(string s) 
{
    vector<ll> dp(s.length()+1);
    for(int i = 1; i <= s.length(); i++)
    {
        dp[i] = INT_MAX;
        for(int j = 1; j <= i; j++)
        {
            if( s[j-1] == '0')
            {
                continue;
            }
            ll num = stoll(s.substr(j-1, i-j+1), nullptr, 2);
            if(isPowerOfFive(num))
            {
                dp[i] = min(dp[i], dp[j-1]+1);
            }
        }
    }
    if(dp[s.length()] == INT_MAX)
    {
        return -1;
    }
    else
    {
        return dp[s.length()];
    }
}
int main()
{
    string s;
    cin>>s;
    cout<<solve(s);
}

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

Check if binary string can be partitioned such that each partition is a power of 5

algorithm

recursion

dynamic-programming

编辑：