回文字符串算法

1. 回文算法

回文指从左往右和从由往左读到相同内容的文字。比如: aba，abba，level。
回文具有对称性。
回文算法的目标是把最长的回文从任意长度的文本当中寻找出来。比如：从123levelabc中寻找出level。

参考资料

通过定义一个s字符数组，gets函数控制输入
i、j双指针来回判断字符数组的位置，和对应位置的值的比较，
while循环的条件 i<=j&&s[i]==s[j]
最终判断i、j的关系，如果i<=j说明存在对应位置不等的情况就是不是回文串

参考资料

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

注意看实现思路
参考

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

输入: "cbbd"
输出: "bb"

解题思路：

参考

解题思路：

1.双重for循环+判别回文串
2.单纯for循环+中心扩散法
3.动态规划

参考

大神Leetcode

2. 数据结构练习：试写一个算法判定给定的字符串是否为回文。在线等 急

java写的

import java.util.Scanner;

public class Echo {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String oneLine;
/* 循环获取输入 */
while (!(oneLine = in.nextLine()).equals("")) {
/* 将字符串转换成char数组 */
char[] line = oneLine.toCharArray();
int begin = 0;
int end = line.length - 1;
boolean result = true;
/* 双向游标比较字符 */
while (begin <= end) {
if (line[begin] == line[end]) {
begin++;
end--;
continue;
} else {
result = false;
break;
}
}
System.out.println(result);
}
}
}

3. 仅使用栈和队列,编写一个算法来判断一个字符串是否为回文.

如果栈和队列都要用到的话，先将字符串全部入队，然后将一半(n/2)的字符出队并且压入栈中，如果字符总数为奇数则丢弃队列中第一个字符，然后将一个字符出队，一个字符出栈，比较，循环，结束。

4. 回文序列问题

Example 1:
Input: 121
Output: true
Example 2:
Input: -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
时间复杂度： O(n^2) 两个for循环
空间复杂度： O(n^2) dp数组的大小

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
示例 1：
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
思路：动态规划得到每个子串是否为回文子串，然后从头开始回溯算法
时间复杂度：O(N * 2^N)

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。
返回符合要求的 最少分割次数 。
示例 1：
输入：s = "aab"
输出：1
解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。
思路：

时间复杂度=空间复杂度=O(n^2)

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例 1：
输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
示例 1：
输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。

给定一个字符串 S，找出 S 中不同的非空回文子序列个数，并返回该数字与 10^9 + 7 的模。
通过从 S 中删除 0 个或多个字符来获得子序列。
如果一个字符序列与它反转后的字符序列一致，那么它是回文字符序列。
如果对于某个 i，A_i != B_i，那么 A_1, A_2, ... 和 B_1, B_2, ... 这两个字符序列是不同的。
示例 1：
输入：
S = 'bccb'
输出：6
解释：
6 个不同的非空回文子字符序列分别为：'b', 'c', 'bb', 'cc', 'bcb', 'bccb'。
注意：'bcb' 虽然出现两次但仅计数一次。

5. 巧用贪心算法，计算出字符串回文

给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。

在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。

注意:
假设字符串的长度不会超过 1010。

示例 1:

输入:
"abccccdd"

输出:
7

解释:
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。

给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。

请注意！！！

题目的意思是：利用这个字符串中的所有字母来构造最长回文串，是构造！是可以改变字母出现的位置顺序的！字母位置可以任意移动。而不是在顺序不变的情况下找出最长的回文串。

作者一开始粗心大意没理解题意，直接上手做题吃大亏（捂脸。

现在来解释下，什么是回文？

回文串是一个正着读和反着读都一样的字符串。

来看两个不同的回文例子：

AB|BA。仅看字母，我们发现，AB和BA根据中心竖线|对称，这个回文串长度为4，每个字母出现的次数都是偶数。
ABCBA。我们发现，AB和BA根据字母C对称，这个回文串长度为5，除了对称中心的字母C仅出现过一次外，中心两边的字母出现次数都是偶数。
所以我们可以总结出，如果想要构造出一个回文串，除了回文串中心的字母只能出现一次外（如果有中心字母的话），中心两边的字母还需对称出现，即出现偶数次。

解决了构造回文串这一关键点，题目中还有一个特别之处：仅出现大写字母和小写字母。

如果对英文字母的Unicode编码熟悉的话，可以知道，字母A的Unicode编码是65（十进制），字母Z的Unicode编码是90（十进制），字母a的Unicode编码是97（十进制）,字母z的Unicode编码是122（十进制）。

可以发现它们是Unicode编码是连续（中间的91到96并不重要），即有序的，所以可以使用数组来存放它们，每个数组项的值就是每个字母出现的次数。

这种情况下，使用数组来存储，会比使用哈希表（Map）来存储来得更高性能，哪怕Unicode编码的91到97我们无需使用。

且，在JavaScript世界中，可以使用String.prototype.charCodeAt()这一API来获取Unicode编码单元。

所以，我们可以这样来统计每个字母出现的次数：

6. 一个包含大写和小写字母的字符串，要求在其后面加上最少的字符，使其成为一个回文串。

program cs;

end;

//删去奇数个字符中间字符。

i:=0;j:=1;

while j<=length(c) do

s[i]:=c[j];

inc(j);

end//栈空，则直接压栈。

else

begin

if s[i]=c[j] then

begin

dec(i);

inc(j);

end//栈顶元素与当前字符相同，就出栈。

end;//不同，就进栈。

if i=0 then writeln('True')

else writeln('False');//如果栈是空的，证明是回文。

思路是对于奇数个字符，删去中间字符。

其余字符扫一个处理一个，s[]是栈，i是它的指针。

j是c的指针。

例如：

对于 ab 字符串，本身不是回文串（反过来是字符串：ba），但是通过在小写字母 b 的后面添加一个小写字母 a，可以使其成为回文串，即：aba（正向、反向内容都相同）

但是对于 abcd 字符串，本身不是回文串（反过来是字符串：dcba），但是无论通过什么方法，都无法做到只添加一个字母，使其成为一个回文串。

(6)回文字符串算法扩展阅读：

1、初始化标志flag=true；

2、输入字符串str，并获取其长度len；

3、定义并初始化游标i=0，j=len-1，分别指向字符串开头和末尾；

4、比较字符str[i]和str[j],若i==j，转至7，否则往下执行5；

5、若str[i]和str[j]相等，则游标i加1，游标j减1后转至4，否则往下执行6；

6、令标志位flag=flase，结束比较，str不是回文串，算法结束。

7、若str[i]和str[j]相等，结束比较，flag=true,str为回文串，算法结束。

7. c语言求回文子串的个数的高效算法

class Palindrome {
public:
int getLongestPalindrome(string A, int n) {
int max=0,count=0;
for(int i=0;i<n;i++) //i作为回文串的中心
{
for(int j=0;((i-j)>=0)&&((i+j)<n);j++)//若回文串是奇数个，i中心前面有j个,后面有j个
{
if(A[i-j]!=A[i+j])
break;
count=j*2+1;
}
if(max<count)
max=count;
for(int j=0;((i-j)>=0)&&((i+1+j)<n);j++)//若回文串是偶数个，i和i+1是中心，前面有j个,后面有j个
{
if(A[i-j]!=A[i+1+j])
break;
count=j*2+2;
}
if(max<count)
max=count;
}
return max;

}

};

8. 使用栈判断给定字符串是否是回文的算法

#include <stdio.h>
#define SIZE 50
int isPalindrome(char str[]);
int elementSize=0;
static int i=0;
int main()
{
int j=0,result;
char element,str[SIZE];
printf("请输入字符串，以回车结束：\n");
/*以下用循环结构读入字符数组的元素，防止了因字符串中含有空格而不能全部读入的情况*/
scanf("%c",&element);
while(element!='\n')
{
str[j]=element;
elementSize++;//记录了数组中已有元素的个数
j++;
scanf("%c",&element);
}

if(isPalindrome(str))
printf("该字符串是回文字符串\n");
else
printf("该字符串不是回文字符串\n");

// system("pause");
return 0;
}
/*函数功能：判断字符串是否为回文串*/
int isPalindrome(char str[])
{
/*把数组元素前后对应比较，即第一个元素与最后一个元素比较是否相等，依此类推*/
if(i>=elementSize-i-1)//说明是回文串
return 1;

else if(str[i]==str[elementSize-i-1])
{
i++;//i为全局静态变量
isPalindrome(str);
}

else //出现不相等的情况，说明不是回文串，返回0
return 0;
}

9. 设计一个算法判断顺序存放的字符串是否为回文

Function Huiwen(a as string) as Boolean
if a=StrReverse(a) then
Huiwen=true
Else
Huiwen=false
End Function

StrReverse 函数 (Visual Basic)
返回指定字符串的字符顺序是相反的字符串。
Public Function StrReverse(ByVal Expression As String) As String
参数
Expression
必选。字符反转的字符串表达式。如果 Expression 是一个零长度字符串 ("")，则返回一个零长度字符串。
备注
StrReverse 函数返回的字符串包含的字符与 Expression 中的字符相同，但字符的顺序相反。

10. 回文字符串——递归

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

int main()
{
int i=0,n,k=0;
char a[20],*p,*q;
scanf("%s",a);
n=strlen(a);
p=a; q=p+n-1;
while(i<(n/2+1)&&q>p)
if(*p==*q) { k++;i++; p++; q--; }
if(k==n/2) printf("Yes\n");
else printf("No\n");

system("pause");
return 0;
}
这是对你的简化版。错误之处一一道来：
1，while语句q>p有错误，因为其后的p，q一直未变。
2，while中i<n多余，只需到n/2+1即可。
3，if语句应该是字符比较 *(p+i)==*(q-i)
4，if语句 { k++; i++; } 必须合在一起，不然i是不变的。
5，if语句，p，q没有变。所以while中只是i<n有效
6，最后判断n%2取余没有比较。