leetcode 5. Longest Palindromic Substring

Seawolf

1. Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
   
2. 
   
3. Example 1:
   
4. 
   
5. Input: "babad"
   
6. Output: "bab"
   
7. Note: "aba" is also a valid answer.
   
8. Example 2:
   
9. 
   
10. Input: "cbbd"
    
11. Output: "bb"

复制代码

Dp

1. class Solution {
   
2.    
   
3.     public String longestPalindrome(String s) {
   
4.         
   
5.         if(s.length() == 0) return s;
   
6.         
   
7.         int len = s.length();
   
8.         
   
9.         int max = 0;
   
10.         
    
11.         String res = "";
    
12.         
    
13.         boolean dp[][] = new boolean[len][len];
    
14.         
    
15.         for(int j = 0; j< len; j++){
    
16.             
    
17.             for(int i = 0 ; i <= j; i++){
    
18.                
    
19.                 dp[i][j] = s.charAt(i)== s.charAt(j) && (j - i <= 2 || dp[i+1][j-1]);
    
20.                     
    
21.                
    
22.                 if(dp[i][j]){
    
23.                     
    
24.                     
    
25.                     if(j - i + 1 > max){
    
26.                     
    
27.                         max = j - i + 1;
    
28.                     
    
29.                         res = s.substring(i,j+1);
    
30.                 }
    
31.                     
    
32.                 }
    
33.                
    
34.                
    
35.             }
    
36.             
    
37.             
    
38.         }
    
39.         
    
40.         return res;
    
41. 
    
42. }
    
43. 
    
44. }

复制代码

1. class Solution {
   
2.    
   
3.     String res = "";
   
4.    
   
5.     public String longestPalindrome(String s) {
   
6.         
   
7.         if(s == null || s.length() == 0) return s;
   
8.         
   
9.         int len = s.length();
   
10.         
    
11.         for(int i = 0; i< len; i++){
    
12.             
    
13.             help(s,i,i);
    
14.             help(s,i,i+1);
    
15.         }
    
16.         
    
17.         return res;
    
18. 
    
19. }
    
20.    
    
21.     public void help(String s, int left, int right){
    
22.         
    
23.         while(left >= 0 && right< s.length() && s.charAt(left) == s.charAt(right)){
    
24.             
    
25.             left --;
    
26.             right++;
    
27.         }
    
28.         
    
29.         String cur = s.substring(left+1, right);
    
30.         
    
31.         if(cur.length() > res.length()){
    
32.             
    
33.             res = cur;
    
34.         }
    
35.     }
    
36.    
    
37. }

复制代码