leetcode 5. Longest Palindromic Substring

Seawolf

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[len][len];
        
        for(int j = 0; j< len; j++){
            
            for(int i = 0 ; i <= j; i++){
                
                dp[i][j] = s.charAt(i)== s.charAt(j) && (j - i <= 2 || dp[i+1][j-1]);
                    
                
                if(dp[i][j]){
                    
                    
                    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;
        }
    }
    
}