string - 将字符串拆分为最少数量的字符串，其中每个字母重复奇数次

Question

例如，字符串 "abab" 需要将一个拆分为两个字符串:"ab" 和 "ab" 所以答案是1 并且字符串“ababab”不需要任何拆分，所以答案是 0。

我想出了一个解决方案，检查每个子字符串的条件并将结果存储在一个 bool 矩阵中，然后填充一个 int 矩阵，以便它找到最少的拆分数。关于如何使算法更快的任何想法？

bool condition(const int count[]) {
    for (int i = 0; i <= 25; i++){
        if (count[i] != 0 && count[i] % 2 == 0) {
            return false;
        }
    }
    return true;
}



int minPartion(std::string& str)
{
    int n = str.size();


    int i, j, k, L;

    int** even = new int*[n];
    for(int i = 0; i < n; ++i)
        even[i] = new int[n];

    int** minSplits = new int*[n];
    for(int i = 0; i < n; ++i)
        minSplits[i] = new int[n];

    for (i = 0; i < n; i++)
    {
        even[i][i] = true;
        minSplits[i][i] = 0;
    }


    for (int i = 0; i < n; i++) {
        int count2[26] = {0};
        for (int j = i; j < n; j++) {
            count2[str[j] - 'a']++;
            even[i][j] = condition(count2);
        }
    }



    for (L = 2; L <= n; L++)
    {
        for (i = 0; i < n - L + 1; i++)
        {
            j = i + L - 1;

            if (even[i][j])
                minSplits[i][j] = 0;
            else
            {
                minSplits[i][j] = INT_MAX;
                for (k = i; k <= j - 1; k++)
                    minSplits[i][j] = min(minSplits[i][j], minSplits[i][k] + minSplits[k + 1][j] + 1);
            }
        }
    }
    
    return minSplits[0][n - 1];
}

Answer 1

一个简单的起点是将计数数组打包成两个 32 位字，一个表示哪些值是非零的，一个表示哪些值是奇数。您可以使用 |= uint32_t{1} << (letter - 'a') 更新这些和 ^= uint32_t{1} << (letter - 'a')然后分别condition变成一个简单的平等测试。