迴文字元串演算法

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取余沒有比較。