给出一个回文字符串,我们可以通过多少方式将其转换为非回文,从中删除一个以上的字符？

Question

给出一个回文字符串,我们可以通过多少方式将其转换为非回文,从中删除一个以上的字符？

例如,如果字符串是"b99b".然后我们可以用6种方式做到

i)删除第一个字符:"99b"
ii)删除第1个,第2个字符:"9b"
iii)删除第1个,第3个字符:"9b"
iv)删除第2个,第4个字符:"b9"
v)删除第3个,第4个字符: "b9"
vi)删除第4个字符:"b99"

如何处理这个？

PS:如果存在i使得索引i处的字符以一种方式被移除而在另一种方式中不被移除,则认为两种方式是不同的.

Answer 1

有一种动态编程算法,用于计算字符串的回文子序列的数量; 您可以使用它来计算非回文子序列的数量,方法是从子序列的数量中减去回文子序列的数量(简单地说是2 ⁿ).O(n2)

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

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

Si,j= S从索引处开始i并以索引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)

Answer 2

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

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

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

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