【常见面试算法】最长回文子串
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public String longestPalindrome(String s) {
if (s.length() == 1 || s.length() == 0) return s;
int len = s.length();
boolean[][] dp = new boolean[len][len];
int beginIndex = 0;
int maxLen = 1;
for (int j = 0; j < len ; j++) {
for (int i = 0 ; i <= j ; i++){
if (s.charAt(i) == s.charAt(j)){
if (j - i < 2){
dp[i][j] = true;
}
else dp[i][j] = dp[i+1][j-1];
}
else dp[i][j] = false;
if (dp[i][j] && j-i+1 > maxLen){
beginIndex = i;
maxLen = j - i + 1;
}
}
}
return s.substring(beginIndex,beginIndex+maxLen);
}
} 
投递旷视等公司10个岗位 >
蓝月亮公司福利 72人发布
