dp第17天

5. 最长回文子串

这题，还是不搞dp了，用中心扩散法来处理，扩散两次，一次当作奇数，一次当作偶数，看哪个得到的结果更大，更新之前的start和maxLen;

len = right – left – 1;

start = i – (len-1)/2 (综合了奇数偶数的结果)

/**
 *
 5. 最长回文子串
 给你一个字符串 s，找到 s 中最长的回文子串。



 示例 1：

 输入：s = "babad"
 输出："bab"
 解释："aba" 同样是符合题意的答案。
 示例 2：

 输入：s = "cbbd"
 输出："bb"


 提示：

 1 <= s.length <= 1000
 s 仅由数字和英文字母组成

 * @author zeroheart
 *
 */
public class Question5 {

   public static String longestPalindrome(String s) {
      int start = 0;
      int maxLen = 0;

      for(int i=0; i<s.length(); i++){
         int len1 = expandAroundCenter(s, i, i);
         int len2 = expandAroundCenter(s, i, i+1);
         int len = Math.max(len1, len2);
         if(len > maxLen){
            start = i - (len-1) / 2 ;
            maxLen = len;
         }
      }

      return s.substring(start, start + maxLen);
   }


   public static int expandAroundCenter(String s, int left, int right) {
      while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
         --left;
         ++right;
      }
      // 跳出循环，s.charAt(left) != s.charAt(right)，所以得到len = right - left - 1;
      return right - left - 1;
   }

   public static void main(String args[]){
//    System.out.println(lengthOfLongestSubstring("abcabcbb"));
//    System.out.println(lengthOfLongestSubstring("bbbbb"));
//    System.out.println(lengthOfLongestSubstring("pwwkew"));
//    System.out.println(lengthOfLongestSubstring("dvdf"));
   }
}

516. 最长回文子序列

// 这题要注意的就是子序列和字串的区别

// 如果i,j对应的char相同，dp[i][j] = dp[i+1][j-1] + 2;
// 如果i,j对应的char不相同，dp[i][j] = max(dp[i+1][j],dp[i][j-1]);

/**
 *
 516. 最长回文子序列
 给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

 子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。



 示例 1：

 输入：s = "bbbab"
 输出：4
 解释：一个可能的最长回文子序列为 "bbbb" 。
 示例 2：

 输入：s = "cbbd"
 输出：2
 解释：一个可能的最长回文子序列为 "bb" 。


 提示：

 1 <= s.length <= 1000
 s 仅由小写英文字母组成

 * @author zeroheart
 *
 */
public class Question516 {

   public int longestPalindromeSubseq(String s) {

      // 这题要注意的就是子序列和字串的区别

      // 如果i,j对应的char相同，dp[i][j] = dp[i+1][j-1] + 2;
      // 如果i,j对应的char不相同，dp[i][j] = max(dp[i+1][j],dp[i][j-1]);


      int len = s.length();
      int[][] dp = new int[len+1][len+1]; // dp[i][j] = dp[i+1][j-1] + 2;  长度多+1

      for(int i = len - 1; i>=0; i--){
         dp[i][i] = 1;
         char ci = s.charAt(i);
         for(int j = i + 1; j<len; j++){
            char cj = s.charAt(j);
            if(ci == cj){
               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 static void main(String args[]){
   }
}