leetcode 5 Longest Palindromic
2020-07-21 本文已影响0人
叫我坤坤
题目
https://leetcode.com/problems/longest-palindromic-substring/submissions/
思路
毫无疑问是动态规划了。用二维数组dp[i][j]记录从i下标到j下标是否为回文子串,则dp[i][j]取值有下面三种情况:
- i==j,此时dp[i][j]=true
- i+1=j,此时dp[i][j]=s[i]==s[j]
- 其余情况,此时dp[i][j]取值为true的条件为:dp[i+1][j-1]=true并且s[i]==s[j]
根据条件直接遍历len就好
代码
public String longestPalindrome(String s) {
int length = s.length();
boolean[][] isPal = new boolean[length][length];
int maxLen = 0;// 记录最长的长度
String answer = ""; // 记录最长的字符串
// 遍历子串的长度
for(int len = 1; len <= length; len++) {
for (int startIndex = 0; startIndex < length; startIndex++) {
//计算起始位置并确保位置合法
int endIndex = startIndex + len - 1;
if (endIndex >= length) {
break;
}
// 核心逻辑
isPal[startIndex][endIndex] = (len == 1) // 长度为1
|| (len == 2 && s.charAt(startIndex) == s.charAt(endIndex)) // 长度为2
|| (isPal[startIndex + 1][endIndex - 1] && s.charAt(startIndex) == s.charAt(endIndex)); // 其他情况
if (isPal[startIndex][endIndex] && len > maxLen) {
maxLen = len;
answer = s.substring(startIndex, endIndex + 1);
}
}
}
return answer;
}