【CT】LeetCode手撕—5. 最长回文子串

---

题目

• 原题连接：5. 最长回文子串

---

1-思路

• 子串的定义：子串是原始字符串的一个连续部分
• 子序列的定义：子序列是原始字符串的一个子集
• 记录最长回文子串的起始位置以及其长度，最终通过下标截取

动规五部曲

• 1.定义 dp 数组
  • boolean dp[i][j] 代表区间在 [i,j] 的子串是否是回文
• 2.递推公式
  • 在 nums[i] == nums[j] 的前提下
  • ① 当 j-1 - (i+1) +1 <2 时，也就是 区间严格小于 2 的时候 j-i<3，dp[i+1][j-1] = true
  • ② 否则 dp[i][j] = dp[i+1][j-1]
• 3.初始化
  • 单个字符一定是回文串：dp[i][i] = true
• 4. 遍历
  • 在得到一个 dp[i][j] 为 true 时，就记录字符串的起始位置和长度
  • 由于 dp[i][j] 从左下角的位置推导来，因此遍历的方式以列遍历，先遍历列再遍历行
  • 由递推公式可以得到，dp[i][j] 由左下角的元素推导而来，因此 i 的遍历顺序是从 s.length() 开始遍历

---

2- 实现

⭐5. 最长回文子串——题解思路

class Solution {public String longestPalindrome(String s) {if(s.length()<2){return s;}int maxLen = 1;int begin = 0;//1. 定义 dp数组// dp[i][j] 代表区间[i,j]内的子串是否回文boolean[][] dp = new boolean[s.length()][s.length()];// 2.递推公式// if(s.charAt(i)==s.charAt(j)) {dp[i][j] = dp[i+1][j-1];}// 3.初始化// dp[i][i] = true;for(int i = 0 ; i < s.length();i++){dp[i][i] = true;}// 4.遍历顺序for(int i = s.length()-1 ; i >= 0 ;i--){for(int j = 0 ; j < s.length();j++ ){if(s.charAt(i) == s.charAt(j)){// 单个字符 没意义if(j-i<3){dp[i][j] = true;}else{dp[i][j] = dp[i+1][j-1];}}// 只要 dp[i][j] == true 成立，就表示 子串[i..j] 回文，此时记录长度和起始位置if(dp[i][j] && j-i+1>maxLen){maxLen = j-i+1;begin = i;}}}return s.substring(begin,begin+maxLen);}
}

---

3- ACM实现

public class maxPlaindrome {public static String maxPlaindrome(String str){int maxLen = 1;int begin = 0;int len = str.length();if(len<2){return str;}//1.定义dpboolean[][] dp = new boolean[len][len];//2.递推// if(s.charAt(i) == s.charAt(j)){ if(j-i>3){dp[i][j]=true;}else{dp[i][j] =dp[i+1][j-1];}}// 初始化for(int i = 0 ; i < len;i++){dp[i][i] = true;}// 4.遍历for(int i = len-1;i>=0;i--){for(int j = 1;j<len;j++){if(str.charAt(i) == str.charAt(j)){if(j-i<3){dp[i][j] = true;}else{dp[i][j] = dp[i+1][j-1];}}if(dp[i][j] && j-i+1>maxLen){maxLen = j-i+1;begin =i;}}}return str.substring(begin,begin+maxLen);}public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("输入字符串");String str = sc.nextLine();System.out.println("最长回文子串为"+maxPlaindrome(str));}
}