Longest Palindromic Substring/Subsequence

Leave a comment

November 3, 2016 by oneOokay

  • Longest Palindromic Substring
  • Longest Palindromic Subsequence
  • Palindromic Substrings

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开始到len - 1结束. 
同时要注意保证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开始视dp的推导公式而定.看里面的for loop里面的i和j的情况
  public String longestPalindrome(String s) {
 if(s == null || s.length() == 0) return s;
 
 int len = s.length();
 String res = "";
 boolean[][] dp = new boolean[len][len];
 for(int i = len - 1; i >= 0; i --){
 for(int j = i; j < len; j ++){
 if (i == j) //case 1
 dp[i][j] = true;
 else if (j == i + 1 && s.charAt(i) == s.charAt(j)) //case 2
 dp[i][j] = true; 
//case 3: 所以j才能够从i开始
 else if (j > i + 1 && dp[i + 1][j - 1] && s.charAt(i) == s.charAt(j))
 dp[i][j] = true;
 if(dp[i][j] && j - i + 1 > res.length())
 res = s.substring(i, j + 1);
 }
 }
 return res;
 }

普通: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还不是非常熟悉的情况下.先分开写,然后在合并优化.

//合并的
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;
//这里j要从i+1开始,因为如果j从i开始的话
//当i=n-1的时候,进入内层循环, i+1会overflow
            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];
    }

Given a string, your task is to count how many palindromic substrings in this string.

The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

Example 1:

Input: "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Example 2:

Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Note:

  1. The input string length won’t exceed 1000.

我感觉这一类的求连在一起的Palindrome都可以先尝试用extend的模板来做. 除了Longest Palindrome Subsequence以外,因为这个的char不是连续的.

方法1: 对于s内的每一个char进行两次extend, 奇数和偶数,然后把返回的结果都加起来即可.

方法2: dp, 就利用Longest Palindromic Substring的想法:

Longest Palindromic Substring: 一个boolean[][] dp矩阵表示了从char i到j这个substring是不是palindrome. 所以我们可以求这么个矩阵同时求累积是palindrome的和既得结果.

 

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 )

Google+ photo

You are commenting using your Google+ 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 )

w

Connecting to %s

%d bloggers like this: