时间戳

首页 > 解决方案 > 返回字符串的散点回文数

c++ - 返回字符串的散点回文数

问题描述

我们必须在给定的字符串中找到散布回文字符串，并返回字符串中散布回文的数量。例如，给定字符串“aabb”，分散回文是 a、aa、aab、aabb、a、abb、b、bb 和 b。这里有 9 个子串是分散回文。

我想到了蛮力方法，即生成所有子字符串并检查它们，但我想找到更好的方法。

标签： c++algorithmc++11data-structuresdynamic-programming

解决方案

首先，让我们考虑如何确定一个字符串是否可以是分散回文。

让我们考虑一下我们的字符串只包含小写字符的情况。

如果满足以下条件，则可以将字符串视为分散回文：

  1. 当字符串长度为偶数时：字符串中出现的所有字符必须出现偶数次。
  2. 当字符串长度为奇数时：字符串中只有一个字符出现奇数次，其他字符出现偶数次。

所以要检查一个字符串是否可以是分散回文，我们只需要检查字符串中每个字符的出现次数。这可以在 O(n) 中完成，其中 n 是字符串的长度。

对于您的解决方案：生成所有子字符串的时间复杂度为 O(n 2 )。为了检查子串是否是分散回文，我们需要另一个 O(n)。因此，总时间复杂度为 O(n 3 )。

我们可以在检查的时候降低 O(n) 因子，这样可以将总时间复杂度降低到 O(n 2 )。

为此，您可以采用大小为 n*26 的二维数组，其中 n 是字符串的长度。设该数组为 A[n][26]。所以 A[i][j] 存储了从 0 到 i 的第 j个字符*的出现总数。

所以对于一个字符串“abca”，你的数组看起来像

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

2 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

现在对于从索引 l 到 r 的任何子字符串，A[r]-A[l-1] 为您提供子字符串中每个字符的出现。要检查这是否可以是分散回文，我们需要 26 次操作。因此，解的时间复杂度变为 O(n 2 * 26)，它与 ​​O(n 2 )渐近相同。

这里我们使用了 n*26 的额外空间。这可以通过更好的方法来避免。

我们不会将每个字符的出现情况存储在数组中，而是将其存储为整数。如果第 j 个索引的第 i个位是 lsb 的“1”，则表示第 i个字符从 0 到第 j个索引出现了奇数次。如果为“0”，则表示第 i个字符*已出现偶数次。

考虑这个输入字符串是“abca”的例子

所以我们的辅助数组将是

1 3 7 6

1 -> (0001) ['a' 出现过一次]

3 -> (0011) ['a' 和 'b' 出现过一次]

7 -> (0111) ['a', 'b' 和 'c' 各出现一次]

6 -> (0110) ['a' 出现了两次，而 'b' 和 'c' 出现了一次]

因此，现在对于从索引 l 到 r A[r] xor A[l-1] 的任何子字符串，如果它是 0 或 2 的幂，则给出将包含在最终答案中的整数。（它具有所有 0 位或只有一个'1' 位）

伪代码如下：

input string = s
ans = 0
n = s.length

for i=1:n
    A[i]=A[i-1]^(1<<(s[i-1]-97))

for i=1:n
    for j=i;n
        x=A[j]^A[i-1]
        if (x&(x-1)) == 0    //if x is a power of 2 or not 
            ans++;
        endif
    endfor
endfor

分散回文的总数存储在ans中。

该方法的空间复杂度为 O(n)。此外，它的运行时间将比之前解释的方法更好。

  • 这里第 i个字符是指考虑 'a' 是第 0个字符，'b' 是第一个字符等的字符。

推荐阅读