2 ways of solving this problem(JAVA) - O(n^2) & O(n^3)


  • 0
    K

    Brute Force - O(n^3) // haven't tried but mostly won't be accepted

    public String LongestPalindrome(String s){
    	int max = 1;
    	int front = 0;
            String ans = "";
    	int back = s.length() - 1;
    	   while(front < s.length() - 1){
    		   while(back > front){
    			   String current = s.substring(front,back+1);
    			   if(isPal(current) && (current.length() > max)){
    				   ans = current;
                                }
    			   back--;	
    		   }
    		   front++;
    	 	   back = s.length() - 1;
    	   }
    	return ans;
    	}
    	public boolean isPal(String s){
    		int i = 0, j = s.length() - 1;
    		while(i < j){
    			if(s.charAt(i) != s.charAt(j))
    				return false;
    			i++;
    			j--;
    		}
    		return true;
    	}
    

    Dynamic Programming - O(n^2)

    public class Solution {
        public String longestPalindrome(String s) {
            int maxLen = 1;
    		int strLen = s.length();
    		int maxPalStart = 0;
    		int i = 0;
    		boolean [][] dp = new boolean[strLen+1][strLen+1];
    		for(i = 0;i < strLen; i++){
    			dp[i][i] = true;
    		}
    		for(i = 0;i < strLen - 1;i++){
    			if(s.charAt(i) == s.charAt(i+1)){
    				dp[i][i+1] = true;
    				maxLen = 2;
    				maxPalStart = i;
    			}
    		}
    		for(int currLen = 3;currLen<=strLen;currLen++){
    			for(i = 0;i < strLen - currLen + 1;i++){
    				int j = i + currLen - 1;
    				if(s.charAt(i) == s.charAt(j) && dp[i+1][j-1]){
    					dp[i][j] = true;
    					maxPalStart = i;
    					maxLen = currLen;
    				}
    			}
    		}
    		return s.substring(maxPalStart,maxPalStart + maxLen);
    		
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.