My O(n2) solution is not working for some reason. Can someone tell why?


  • 0
    P
    public class Solution {
        public static String longestPalindrome(String s) {
    	      String s1 = s;
    	      String s2 = reverse(s);
    	      int max=0;
    	      int maxIndex=0;
    	      int[][] a = new int[s.length()+1][s.length()+1];
    	      for(int i=0;i<=s.length();i++){
    	    	  for(int j=0;j<=s.length();j++){
    	    		  if(i==0 || j==0){
    	    			  a[i][j]=0;
    	    		  }
    	    		  else if(s1.charAt(i-1)==s2.charAt(j-1)){
    	    			  a[i][j] = a[i-1][j-1]+1;
    	    		  }
    	    		  else{
    	    			  a[i][j]=0;
    	    		  }
    	    		  if(a[i][j]>=max){
    	    			  max = a[i][j];
    	    			  maxIndex = i;
    	    		  }
    	    	  }
    	      }
    		 return s.substring(maxIndex-max, maxIndex);
    	 }
    
    	private static String reverse(String s) {
    		StringBuilder sb = new StringBuilder(s);
    		String newS = "";
    		for(int i=sb.length()-1;i>=0;i--){
    			newS += sb.charAt(i);
    		}
    		return newS;
    	}
    }

  • 0
    P

    I have reversed the string and used the longest common substring on it.


Log in to reply
 

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