leetcode 5. Longest Palindromic Substring
本帖最后由 Seawolf 于 2019-8-31 09:54 编辑Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:
Input: "cbbd"
Output: "bb"
Dp
class Solution {
public String longestPalindrome(String s) {
if(s.length() == 0) return s;
int len = s.length();
int max = 0;
String res = "";
boolean dp[][] = new boolean;
for(int j = 0; j< len; j++){
for(int i = 0 ; i <= j; i++){
dp = s.charAt(i)== s.charAt(j) && (j - i <= 2 || dp);
if(dp){
if(j - i + 1 > max){
max = j - i + 1;
res = s.substring(i,j+1);
}
}
}
}
return res;
}
}
class Solution {
String res = "";
public String longestPalindrome(String s) {
if(s == null || s.length() == 0) return s;
int len = s.length();
for(int i = 0; i< len; i++){
help(s,i,i);
help(s,i,i+1);
}
return res;
}
public void help(String s, int left, int right){
while(left >= 0 && right< s.length() && s.charAt(left) == s.charAt(right)){
left --;
right++;
}
String cur = s.substring(left+1, right);
if(cur.length() > res.length()){
res = cur;
}
}
}
页:
[1]