6

给定一个回文字符串，我们可以通过多少种方式通过从中再删除一个字符将其转换为非回文字符串？

例如，如果字符串是“b99b”。然后我们可以通过 6 种方式做到这一点，

i) 删除第一个字符："99b"
ii) 删除第一个、第二个字符："9b"
iii) 删除第一个、第三个字符："9b"
iv) 删除第二个、第四个字符："b9"
v) 删除第三个、第四个字符： "b9"
vi) 删除第 4 个字符："b99"

如何接近这个？

PS：如果存在一个 i 使得索引 i 处的字符以一种方式被删除而不以另一种方式被删除，则两种方式被认为是不同的。

4

5 回答 5

6

有一种动态规划算法用于计算字符串的回文子序列的数量；您可以使用它来计算非回文子序列的数量，方法是从子序列的数量（即 2 n）中减去回文子序列的数量。O(n2)

该算法按 OP 中的标准对子序列进行计数；如果用于选择元素的索引列表存在差异，则认为两个子序列不同，即使结果子序列具有相同的元素。

为了计算回文子序列，我们根据序列的间隔建立计数。具体来说，我们定义：

Si,j=S从 index 开始到 indexi结束的子串j（含）

Pi,j= 的回文子序列的数量Si,j

现在，每个单元素区间都是回文，所以：

Pi,i = 1对所有人i < n

如果子串不是以相同的元素（即）开始和结束，则回文子序列包括：Si ≠ Sj

  • 包含但不包含的SiSj

  • 包含但不包含的SjSi

  • 既不包含也不包含SiSj

现在，注意包括第一组和第三组子序列，同时包括第二组和第三组；正好是第三组。最后：Pi,j-1Pi+1,jPi+1,j-1

Pi,j = Pi+1,j + Pi,j-1 − Pi+1,j-1如果Si ≠ Sj

但万一呢？在这种情况下，我们必须添加由 组成的回文，后跟来自 的子序列回文，以及仅由开始和结束字符组成的回文子序列。（从技术上讲，一个空序列是一个回文，但我们在这里不计算它们。）我们添加的子序列的数量是 P i+1,j-1 + 1，这抵消了上面等式中减去的双重计数。所以：Si = SjSiSi+1,j-1Sj

Pi,j = Pi+1,j + Pi,j-1 + 1如果.Si = Sj

为了节省空间，我们实际上可以计算增加的​​值；我们只需要保留其中两个向量即可生成最终结果 P 0,|S|-1。Pi,i+k for 0 ≤ i < |S|-kk

编辑：

这是一个小python程序；第一个计算回文子序列的数量，如上所述，驱动程序计算非回文子序列的数量（即删除零个或多个元素并产生非回文的方法的数量；如果原始序列是回文，那么它是删除一个或多个元素的方法数。）

# Count the palindromic subsequences of s
def pcount(s):
  length = len(s)
  p0 = [0] * (length + 1)
  p1 = [1] * length
  for l in range(1, length):
    for i in range(length - l):
      p0[i] = p1[i]
      if s[i] == s[i + l]:
        p1[i] += p1[i+1] + 1
      else:
        p1[i] += p1[i+1] - p0[i+1]
  # The "+ 1" is to account for the empty sequence, which is a palindrome.
  return p1[0] + 1

# Count the non-palindromic subsequences of s
def npcount(s):
  return 2**len(s) - pcount(s)
于 2013-02-17T18:07:57.347 回答
2

这不是一个完整的答案，只是一个建议。

我会计算可以删除一个或多个字符并使字符串保持回文的方法的数量。然后从可以修改字符串的方式总数中减去它。

修改回文并使其保持回文的最明显方法是删除i'th和(n-i)'th字符（n 是字符串的长度）。有一些2^(n/2)方法可以做到这一点。

这种方法的问题在于它假设只有对称修改才能使字符串保持回文，您需要找到一种方法来处理诸如"aaaa"任何类型的修改仍会导致回文的情况。

于 2013-02-17T12:43:27.910 回答
1

使用记忆的蛮力非常简单：

numWays(str): return 0 if str is empty
              return memo[str] if it exists
              memo[str] = numWays(str - firstChar) +
                          numWays(str - secondChar) +
                          ... +
                          1 if str is not a palindrome
              return memo[str]

基本上，您依次删除每个字符并保存结果字符串的答案。字符串中的相同字符越多，速度就越快。

我不确定如何更有效地做到这一点，如果我弄明白了，我会更新这个。

于 2013-02-17T14:34:01.390 回答
1

对于具有 N 个元素的字符串，有 2^N 个可能的子字符串（包括整个字符串和空子字符串）。因此，我们可以用一个数字对每个子字符串进行编码，在每个省略（或存在）的字符的位位置上使用“1”位，否则为“0”位。（假设字符串的长度小于 int 中的位数（此处为 size_t），否则您将需要位串的其他表示形式）：

#include <stdio.h>
#include <string.h>

char string[] = "AbbA";
int is_palindrome (char *str, size_t len, size_t mask);

int main(void)
{
size_t len,mask, count;

len = strlen(string);

count =0;
for (mask = 1; mask < (1ul <<len) -1; mask++) {
        if ( is_palindrome (string, len, mask)) continue;
        count++;
        }

fprintf(stderr, "Len:=%u, Count=%u \n"
        , (unsigned) len , (unsigned) count );

return 0;
}

int is_palindrome (char *str, size_t len, size_t mask)
{
size_t l,r,pop;

for (pop=l=0, r = len -1; l < r; ) {
        if ( mask & (1u <<l)) { l++; continue; }
        if ( mask & (1u <<r)) { r--; continue; }
        if ( str[l] == str[r] ) return 1;
        l++,r--; pop++;
        }
return (pop <1) ? 1: 0;
}
于 2013-02-17T15:32:41.800 回答
0

这是一个 Haskell 版本：

import Data.List

listNonPalindromes string = 
  filter (isNotPalindrome) (subsequences string)
    where isNotPalindrome str
            | fst substr == snd substr  = False
            | otherwise                 = True
           where substr = let a = splitAt (div (length str) 2) str
                          in (reverse (fst a), if even (length str) 
                                                  then snd a 
                                                  else drop 1 (snd a))

howManyNonPalindromes string = length $ listNonPalindromes string

*Main> listNonPalindromes "b99b"
["b9","b9","b99","9b","9b","99b"]
*Main> howManyNonPalindromes "b99b"
6

于 2013-02-17T16:50:49.627 回答