關(guān)于我的 Leetcode 題目解答局嘁，代碼前往 Github：https://github.com/chenxiangcyr/leetcode-answers
問題：給出一個字符串 S，找到在 S 中的最長的回文子串巢掺。
LeetCode題目：5. Longest Palindromic Substring
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
算法對比：
-
暴力枚舉法
- O(N3)
- 遍歷所有子字符串，子串數(shù)為 N2，長度平均為 N/2
-
動態(tài)規(guī)劃法
- O(N2)
- 兩層循環(huán)礁凡，外層循環(huán)從后往前掃叠赐，內(nèi)層循環(huán)從當前字符掃到結(jié)尾處，省略已經(jīng)判斷過的記錄
-
中心檢測法
- O(N2)
- 分奇偶兩種情況撒汉，以
i為中心不斷向兩邊擴展判斷，無需額外空間
-
馬拉車算法
- O(N)
- 從左到右掃描涕滋，省略已經(jīng)判斷過的記錄睬辐，線性
動態(tài)規(guī)劃法
// DP Solution
public String longestPalindromeDP(String s) {
if(s.isEmpty()) return "";
int n = s.length();
String result = null;
// dp[i][j] 表示第i個字符到第j個字符是否為回文
boolean[][] dp = new boolean[n][n];
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || dp[i + 1][j - 1]);
if (dp[i][j] && (result == null || j - i + 1 > result.length())) {
result = s.substring(i, j + 1);
}
}
}
return result;
}
中心檢測法
// 中心檢測法
public String longestPalindromeCenter(String s) {
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
/*
一個回文字符串可以從中心向兩邊擴展，會有 2n - 1 個中心宾肺，而不是 n 個中心溯饵。
因為中心可以存在于兩個字符中間，例如 abba锨用，中心在b和b中間丰刊。
*/
// 以第i個字符為中心向兩邊擴展
int len1 = expandAroundCenter(s, i, i);
// 以第i個字符和第i+1個字符的中間為中心向兩邊擴展
int len2 = expandAroundCenter(s, i, i + 1);
int len = Math.max(len1, len2);
if (len > end - start) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
return s.substring(start, end + 1);
}
private int expandAroundCenter(String s, int left, int right) {
int L = left, R = right;
while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
L--;
R++;
}
return R - L - 1;
}
Manacher's Algorithm 馬拉車算法
預處理1：解決字符串長度奇偶問題
馬拉車算法可以看成是中心檢測法的升級版本，在上面的表格中提到中心檢測法是需要區(qū)分奇偶兩種情況的黔酥，那么在馬拉車算法中首先要解決的就是這個問題藻三。
這里首先對字符串做一個預處理，在所有的空隙位置（包括首尾）插入同樣的符號跪者。無論原字符串是奇數(shù)還是偶數(shù)棵帽，通過這種做法，都會使得處理過的字符串變成奇數(shù)長度渣玲。
以插入#號為例：
123（長度為3） -> #1#2#3# （長度為7）
abccba （長度為6）-> #a#b#c#c#b#a#（長度為13）
我們把一個回文串中最左或最右位置的字符與其對稱軸的距離稱為回文半徑逗概。
馬拉車算法定義了一個回文半徑數(shù)組 p，用 p[i] 表示以第 i 個字符為對稱軸的回文串的回文半徑忘衍。
例如：
字符串 T = # a # b # a # a # b # a #
半徑數(shù)組P = 0 1 0 3 0 1 6 1 0 3 0 1 0
Looking at P, we immediately see that the longest palindrome is “abaaba”, as indicated by P6 = 6
為了進一步減少編碼的復雜度逾苫，可以在字符串的開始加入另一個特殊字符，這樣就不用特殊處理越界問題枚钓，比如$#a#b#a#
// Manacher's Algorithm 馬拉車算法
public String longestPalindromeManacher(String s) {
if (s.length() <= 1) {
return s;
}
// 解決字符串長度奇偶問題
StringBuilder stringBuilder = new StringBuilder("$");
for (char c : s.toCharArray()) {
stringBuilder.append("#");
stringBuilder.append(c);
}
stringBuilder.append("#");
String str = stringBuilder.toString();
int id = 0;
int idMax = 0;
int index = 0;
int maxLength = 0;
int p[] = new int[str.length()];
// 遍歷每一個字符
for (int curr = 1; curr < str.length(); curr++) {
// j 是 curr 關(guān)于 id 的對稱點
int j = 2 * id - curr;
// 如果 idMax > curr铅搓，那么P[curr] >= MIN(P[j], idMax - curr)
if (idMax > curr) {
if (p[j] < idMax - curr)
p[curr] = p[j];
else
p[curr] = idMax - curr;
} else {
p[curr] = 1;
}
while (curr + p[curr] < str.length() && str.charAt(curr + p[curr]) == str.charAt(curr - p[curr])) {
p[curr]++;
}
if (curr + p[curr] > idMax) {
id = curr;
idMax = curr + p[curr];
}
if (p[curr] > maxLength) {
maxLength = p[curr];
index = curr;
}
}
return s.substring((index - maxLength) / 2, (index + maxLength) / 2 - 1);
}
其他回文字符串題目
LeetCode題目：131. Palindrome Partitioning
Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
Example:
Input: "aab"
Output:
[
["aa","b"],
["a","a","b"]
]
class Solution {
public List<List<String>> allPartition = new ArrayList<List<String>>();
public List<String> onePartition = new ArrayList<String>();
public List<List<String>> partition(String s) {
travel(s.toCharArray(), 0);
return allPartition;
}
public void travel(char[] arr, int startIdx) {
for(int i = startIdx; i < arr.length; i++) {
if(isPalindrome(arr, startIdx, i)) {
String str = new String(Arrays.copyOfRange(arr, startIdx, i + 1));
onePartition.add(str);
// to the end
if(i == arr.length - 1) {
allPartition.add(new ArrayList(onePartition));
}
else {
travel(arr, i + 1);
}
// backtracking
onePartition.remove(onePartition.size() - 1);
}
}
}
public boolean isPalindrome(char[] arr, int startIdx, int endIdx) {
while(startIdx <= endIdx && arr[startIdx] == arr[endIdx]) {
startIdx++;
endIdx--;
}
return startIdx >= endIdx;
}
}
LeetCode題目：132. Palindrome Partitioning II
Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
Example:
Input: "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.
class Solution {
public int minCut(String s) {
return travel(s, 0,0, new HashMap<>());
}
public int travel(String s, int pos, int cut, Map<Integer,Integer> cache) {
if(pos>=s.length()) {
return cut - 1;
}
int min = Integer.MAX_VALUE;
if(cache.containsKey(pos)) {
return cut + cache.get(pos);
}
for(int end = pos + 1; end <= s.length(); ++end){
String sub = s.substring(pos, end);
if(isPalindrome(sub)) {
min = Math.min(min, travel(s, end, cut+1, cache));
}
}
cache.put(pos, min - cut);
return min;
}
public boolean isPalindrome(String s) {
int startIdx = 0;
int endIdx = s.length() - 1;
while(startIdx <= endIdx && s.charAt(startIdx) == s.charAt(endIdx)) {
startIdx++;
endIdx--;
}
return startIdx >= endIdx;
}
}
LeetCode題目：214. Shortest Palindrome
Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.
For example:
Given "aacecaaa", return "aaacecaaa".
Given "abcd", return "dcbabcd".
代碼如下，時間復雜度O(n^2)：
class Solution {
public String shortestPalindrome(String s) {
if(s == null || s.length() <= 1) return s;
// 找到s中包含第一個字符的最長回文子串
int right = s.length() - 1;
while(right > 0 && !isPalindrome(s, 0, right)) {
right--;
}
// 最壞情況 right = 0搀捷，例如abc
StringBuilder sb = new StringBuilder();
for(int i = s.length() - 1; i > right; i--) {
sb.append(s.charAt(i));
}
sb.append(s);
return sb.toString();
}
public boolean isPalindrome(String s, int start, int end) {
while(start <= end) {
if(s.charAt(start) != s.charAt(end)) {
return false;
}
start++;
end--;
}
return true;
}
}
對于此題星掰，有時間復雜度為O(n)的算法，利用了 KMP 算法嫩舟，思路參考https://leetcode.com/articles/shortest-palindrome/氢烘，代碼如下：
public class Solution {
class Solution {
public String shortestPalindrome(String s) {
String temp = s + "#" + new StringBuilder(s).reverse().toString();
int[] table = getTable(temp);
return new StringBuilder(s.substring(table[table.length - 1])).reverse().toString() + s;
}
public int[] getTable(String s){
int[] table = new int[s.length()];
table[0] = 0;
for(int i = 1; i < s.length(); i++)
{
int t = table[i - 1];
while(t > 0 && s.charAt(i) != s.charAt(t)) {
t = table[t - 1];
}
if(s.charAt(i) == s.charAt(t)) {
t++;
}
table[i] = t;
}
return table;
}
}
LeetCode題目：125. Valid Palindrome
Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.
class Solution {
public boolean isPalindrome(String s) {
// we define empty string as valid palindrome
if(s.isEmpty()) {
return true;
}
char[] arr = s.toCharArray();
int i = 0;
int j = arr.length - 1;
while(i < j) {
Character ci = new Character(arr[i]);
Character cj = new Character(arr[j]);
// considering only alphanumeric characters
if(!Character.isDigit(ci) && !Character.isLetter(ci)) {
i++;
continue;
}
if(!Character.isDigit(cj) && !Character.isLetter(cj)) {
j--;
continue;
}
// ignoring cases
if(Character.toUpperCase(ci) != Character.toUpperCase(cj)) {
return false;
}
i++;
j--;
}
return true;
}
}
LeetCode題目：680. Valid Palindrome II
Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.
Example 1:
Input: "aba"
Output: True
Example 2:
Input: "abca"
Output: True
Explanation: You could delete the character 'c'.
Note:
- The string will only contain lowercase characters a-z. The maximum length of the string is 50000.
class Solution {
public boolean validPalindrome(String s) {
if(s.isEmpty()) return true;
int i = 0;
int j = s.length() - 1;
while(i < j) {
if(s.charAt(i) != s.charAt(j)) {
return validPalindrome(s, i + 1, j) || validPalindrome(s, i, j - 1);
}
i++;
j--;
}
return true;
}
public boolean validPalindrome(String s, int from, int to) {
while(from < to) {
if(s.charAt(from) != s.charAt(to)) {
return false;
}
from++;
to--;
}
return true;
}
}
LeetCode題目：266. Palindrome Permutation
Given a string, determine if a permutation of the string could form a palindrome.
For example,
"code" -> False, "aab" -> True, "carerac" -> True.
class Solution {
public boolean canPermutePalindrome(String s) {
// key: char, value: count
Map<Character, Integer> map = new HashMap<>();
for(char c : s.toCharArray()) {
map.put(c, map.getOrDefault(c, 0) + 1);
}
// 出現(xiàn)次數(shù)為奇數(shù)次的字符的個數(shù)
int oddOccur = 0;
for(Integer count : map.values()) {
// 出現(xiàn)了奇數(shù)次
if(count % 2 == 1) {
oddOccur++;
}
if(oddOccur > 1) {
return false;
}
}
return true;
}
}
引用：
Manacher's Algorithm 馬拉車算法
[Swift 算法] 馬拉車算法
Longest Palindromic Substring Part II
Manacher's ALGORITHM: O(n)時間求字符串的最長回文子串
