通过从字符串中选择字符可以形成多少回文？

首先，您朋友的解决方案似乎存在错误，因为

strchr

max

对于更快的解决方案，您可以使用动态编程在O（n ^
3）时间内解决此问题。这将需要O（n ^ 2）额外的内存。请注意，对于长字符串，即使是我这里使用的64位整数也不足以容纳解决方案。

#define MAX_SIZE 1000long long numFound[MAX_SIZE][MAX_SIZE]; //intermediate results, indexed by [startPosition][endPosition]long long countPalindromes(const char *str) {    int len = strlen(str);    for (int startPos=0; startPos<=len; startPos++)        for (int endPos=0; endPos<=len; endPos++) numFound[startPos][endPos] = 0;    for (int spanSize=1; spanSize<=len; spanSize++) {        for (int startPos=0; startPos<=len-spanSize; startPos++) { int endPos = startPos + spanSize; long long count = numFound[startPos+1][endPos];   //if str[startPos] is not in the palindrome, this will be the count char ch = str[startPos]; //if str[startPos] is in the palindrome, choose a matching character for the palindrome end for (int searchPos=startPos; searchPos<endPos; searchPos++) {     if (str[searchPos] == ch)         count += 1 + numFound[startPos+1][searchPos]; } numFound[startPos][endPos] = count;        }    }    return numFound[0][len];}

说明：

该数组

numFound[startPos][endPos]

我们遍历所有索引对（startPos，endPos），从短跨度开始，然后过渡到更长的对。对于每个这样的对，都有两个选项：

1. 处的字符

   str[startPos]

   不在回文中。在这种情况下，

   numFound[startPos+1][endPos]

   可能存在回文-我们已经计算出一个数。

2. 字符位于

   str[startPos]

   回文（开始时）。我们扫描字符串以找到匹配的字符并放在回文末尾。对于每个这样的角色，我们使用已经计算出的结果

   numFound

   来寻找内部回文的可能性。

编辑 ：

• 澄清：当我说“字符串中包含的回文数”时，其中包括不连续的子字符串。例如，回文“ aba”包含在“ abca”中。

• 通过利用

  numFound[startPos][x]

  仅计算

  numFound[startPos+1][y]

  y就需要y 的事实，可以将内存使用量减少到O（n）。我不会在这里做这件事，因为它会使代码复杂一些。

• 包含每个字母的索引的预生成列表可以使内部循环更快，但总体上仍为O（n ^ 3）。