Longest Palindromic

Leave a comment

November 3, 2016 by oneOokay

  • Longest Palindromic Substring
  • Longest Palindromic Subsequence

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.

Example:

Input: "cbbd"

Output: "bb"

DP和普通方法(extend palindrome):

DP:(一个由内向外扩散的推导关系)

推导公式: DP[i,j](boolean)表示从S[i]到S[j]是否是一个Palindrome.(其中S[i]是string.toCharArray)

  • = TRUE if i ==j
  • = (S[i] ==S[j])  if j = i+1
  • = (S[i] == S[j] && DP[i+1][j-1]) if j>i+1

第三个推导公式: 与dp[i+1][j-1]相关,是一个由内向外扩散的递推关系.这里需要在扩大i,j的范围前,要确保i,j里头范围内的所有值已经取过了.

i为,j为:i从string的最后一个开始; j始终从i开始. 
同时要注意保证dp[i][j]i为"头"j为"尾"
for(int i = s.size() - 1; i >=0 ; i--){
for (int j = i/i+1; j < s.size(); j ++)...}//这里j从i或者i+1开始视情况而定

另一个for-loop循环方法是:

  • for (int j = 0; j < n; j ++){ for (int i = j; i >= 0; i –) …}
  • 外层从0开始递增:此时外层为尾部,所以为j:因为外层每+1,内层首先要和外层保持一致,之后再逐渐-,此时内层比外层小,所以内层为i。
public String longestPalindrome(String s) {
        if(s == null || s.length() <= 1) return s;
         int n = s.length();
         char[] c = s.toCharArray();
         int maxLength = 0;
         String result = "";
         boolean[][] dp = new boolean[n][n];
         for (int i = n - 1; i >= 0; i --){
            for (int j = i; j < n; j ++){
//注意这里与subsequence那题的区别
                 if (i == j || (i + 1 == j && c[i] == c[j]) ||
//为了确保dp[i+1][j-1]满足为"头"和"尾"的条件
                 (j > i + 1 && dp[i + 1][j - 1] && c[i] == c[j])){
                    dp[i][j] = true;
                    if (j - i + 1 > maxLength){
                        maxLength = j - i + 1;
                        result = s.substring(i, j + 1);
                    }
                }
            }
        }
        return result;
    }

普通:extendPalindrome

思路是for loop遍历每个char,以每一个char为可能的palindrome的中间,开始extend出去,看它能够extend构成的最长的palindrome。

  • 注意extend的时候要考虑两个情况:
    • 奇数的Palindrome:当前char为中点
    • 偶数的Palindrome:当前char和之后的一个char为中点
  • 已知中点,从中点开始判断、取得palindrome,用双指针!!!
  • JAVA: str.substring(start, end):两个参数均为index,其中[start, end)
public class Solution {
 public String longestPalindrome(String s) {
 if (s == null || s.length() <= 1) return s;
 String result = "";
 String tmp = "";
 for(int i = 0; i < s.length(); i ++){  tmp = getPalindrome(i, i, s);//奇数Palindrome  if (tmp.length() > result.length())
 result = tmp;
 tmp = getPalindrome(i, i + 1, s);//偶数Palindrome
 if (tmp.length() > result.length())
 result = tmp;
 }
 return result;
 }
 
 private String getPalindrome(int start, int end, String s){
 while (start >= 0 && end <= s.length() - 1 
&& s.charAt(start) == s.charAt(end)){
 start --;
 end ++;
 } //这段要随时写出来吧
//注意这里break出来的start和end是不满足情况的,所以正确的值应该是start+1和end-1.
//但是由于substring的endIndex是exclusive的,所以是substring(start+1,end)
 return s.substring(start + 1, end);
 }
}

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”.


这题跟上题的区别是:上题是substring,不能跳过char,而这题可以.

容易想到dp,因为dfs不适合…但是我想不到推导公式.因为我没有一个extend palindrome的思维.

dp的话推导公式还挺简单:dp[i][j] (int[][])代表从i到j中存在的最长的Palindrome的长度

  • 初始化dp[i][i]=1
  • =dp[i+1][j-1] + 2 if (s[i] == s[j])如果
  • =Math.max(dp[i+1][j], dp[i][j-1]) if (s[i] !=s[j])
    • 当s[i]和s[j]不等的时候,如果longest palindrome有变化的话有3种情况:
      1. s[i]为新的Palindrome的一部分而s[j]不是:此时=dp[i][j – 1]
      2. s[j]为新的Palindrome的一部分而s[i]不是:此时=dp[i+1][j]
      3. s[i]和s[j]都不是Palindrome的一部分:此时=dp[i+1][j-1].由于区间[i,j+1]和区间[i+1,j]都包含了区间[i+1,j-1],所以dp[i][j – 1]和dp[i+1][j]必然都>=dp[i+1][j-1].这样的话第三种情况就不用考虑了.

同样的是一个由内区间向外区间推导的情况,注意写法:还是比较建议初始化和处理分开写…在对dp还不是非常熟悉的情况下.先分开写,然后在合并优化.

//i从最后一个char开始,且为外圈,逐渐扩大,所以i可以取到0. 
for (int i = len - 1; i >= 0; i --){
//j为里圈: j必须从i+1开始. 
//j == i的情况已经被初始化了,值应该为1.而且如果j==i的话永远会进入+2的那个if
//是错误的.并且i是从len-1开始,那么dp[i+1][j-1]会出界.
//所以这里j=i+1
 for (int j = i + 1; j < len; j ++){
 if (s.charAt(i) == s.charAt(j)){
 dp[i][j] = dp[i + 1][j - 1] + 2;
 }else {
 dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
 }}}
 return dp[0][len - 1];
 }

//合并的
public int longestPalindromeSubseq(String s) {
        if(s == null || s.length() == 0) return 0;
        int n = s.length();
        int[][] dp = new int[n][n];
        for (int i = n - 1; i >= 0; i --){
            dp[i][i] = 1;
            for (int j = i + 1; j < n; j ++){
                if (s.charAt(i) == s.charAt(j)){
                    dp[i][j] = dp[i + 1][j - 1] + 2; 
                }else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j -1]);
                }
            }
        }
        return dp[0][n - 1];
    }
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: