1. Palindrome Partitioning
Given a strings, partitionssuch that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
For example, givens="aab",Return
[
["aa","b"],
["a","a","b"]
]
public class Solution {
boolean[][] dp;
int n;
public List<List<String>> partition(String s) {
n = s.length();
ArrayList<List<String>> ans = new ArrayList<>();
if(n == 0) return ans;
detectPalindrome(s);//1
dfs(s, 0, new ArrayList<>(), ans);//2
return ans;
}
public void detectPalindrome(String s) {
dp = new boolean[n][n];
for(int i = 0; i < n; i ++)
dp[i][i] = true;
for(int j = 0; j < n; j ++){
for(int i = 0; i < j; i ++){
dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i + 1][j - 1]);
}
}
}
public void dfs(String s, int i, List<String> sub, ArrayList<List<String>> ans) {
if(i == n){
ans.add(new ArrayList<>(sub));
return;
}
for(int j = i; j < n; j ++){
if(dp[i][j]){
String s2 = s.substring(i, j+1);
sub.add(s2);
dfs(s, j + 1, sub, ans);
sub.remove(sub.size() - 1);
}
}
}
}
2. Palindrome Partitioning II
Given a strings, partitionssuch that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning ofs.
For example, givens="aab",
Return1since the palindrome partitioning["aa","b"]could be produced using 1 cut.
public class Solution {
public int minCut(String s) {
if(s.length() == 0)
return 0;
int n = s.length();
int[] cuts = new int[n];
boolean[][] dp = new boolean[n][n];
int min;
for(int i = 0; i < n; i ++)
dp[i][i] = true;
for(int j = 0; j < n; j ++){
min = j;
for(int i = 0; i < j; i ++){
dp[i][j] = s.charAt(i) == s.charAt(j) && (j-i<2 || dp[i+1][j-1])
if(dp[i][j]){
min = i == 0? 0: Math.min(min, cuts[j-1] + 1);
}
}
curs[j] = min;
}
return cuts[n - 1];
}
}
3. Longest Palindromic Substring
Given a string s, find the longest palindromic substring in s
public class Solution {
public String longestPalindrome(String s) {
if(s.length() <= 1) return s;
int n = s.length();
boolean[][] dp = new boolean[n][n];
int left = 0, right = 0, longest = 0;
for(int len = 0; len < n; len ++) {
for(int i = 0, j = len; j < n; i ++, j ++) {
dp[i][j] = s.charAt(i) == s.charAt(j) && (j-i<2 || dp[i+1][j-1]);
if(dp[i][j] && j-i> longest){
longest = j - i;
left = i;
right =j;
}
}
}
/*
for(int i = 0; i < n; i ++)
dp[i][i] = true;
for(int j = 0; j < n; j ++){
for(int i = 0; i < j; i ++){
dp[i][j] = s.charAt(i) == s.charAt(j) && (j-i<2 || dp[i+1][j-1]);
if(dp[i][j] && j - i > longest){
longest = j - i;
left = i;
right= j;
}
}
}
*/
return s.substring(left, right+1);
}
}
Solution 2:
public class Solution {
int start;
int len = 0;
int n;
public String longestPalindrome(String s) {
if(s.length() <= 1) return s;
n = s.length();
for(int i = 0; i < n - 1; i++ ){
if(s.charAt(i) == s.charAt(i+1))
search(s, i, i+1);
search(s, i, i);
}
return s.substring(start, start + len);
}
public void search(String s, int left, int right) {
int step = 1;
while(left - step >= 0 && right + step < n){
if(s.charAt(left - step) != s.charAt(right + step))
break;
step ++;
}
int wide = right - left + 1 + 2 * (step - 1);
if(wide > len){
len = wide;
start = left - (step - 1);
}
}
}
*** Manacher's Algorithm
***4. 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".
public class Solution {
public String shortestPalindrome(String s) {
int i=0;
int j=s.length()-1;
while(j>=0){
if(s.charAt(i)==s.charAt(j)){
i++;
}
j--;
}
if(i==s.length())
return s;
String suffix = s.substring(i);
String prefix = new StringBuilder(suffix).reverse().toString();
String mid = shortestPalindrome(s.substring(0, i));
return prefix + mid + suffix;
}
}
5 Longest Palindromic Subsequence
Given a string s, find the longest palindromic subsequence's length in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: "bbbab"
Output:4
One possible longest palindromic subsequence is "bbbb".
Example 2:
Input: "cbbd"
Output: 2
One possible longest palindromic subsequence is "bb".
public class Solution {
public int longestPalindromeSubseq(String s) {
if(s.length() == 0) return 0;
Integer[][] memo = new Integer[s.length() ][s.length() ];
return LPS(s, 0, s.length() - 1, memo);
}
public int LPS(String s, int i, int j, Integer[][] memo) {
if(memo[i][j] != null) return memo[i][j];
if(i > j) return 0;
if(i == j) return 1;
if(s.charAt(i) == s.charAt(j))
memo[i][j] = LPS(s, i + 1, j - 1, memo) + 2;
else
memo[i][j] = Math.max(LPS(s, i + 1, j, memo), LPS(s, i, j-1, memo));
return memo[i][j];
}
}
public class Solution {
public int longestPalindromeSubseq(String s) {
int n = s.length();
if(n <= 1) return n;
int[][] dp = new int[n][n];
for(int len = 0; len <n; len ++) {
for(int i = 0, j = len; j < n; i ++, j ++) {
if(s.charAt(i) == s.charAt(j)){
if(len < 2)
dp[i][j] = len + 1;
else
dp[i][j] = dp[i + 1][j - 1] + 2;
}
else{
dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]);
}
}
}
return dp[0][n - 1];
}
}