0

I have written the which works fine.

public class Palindrom {    
    public static boolean isPalindrom(String s){
        char[] c = s.toCharArray();
        for(int i =0;i<=(s.length()-1)/2;i++){
            if(c[i]!=c[(s.length()-1)-i]){
                return false;
            }
        }
        return true;
    }
    public static void main(String[] args){
        String s="aba";
        int n=3;
        for(int j=0;j<s.length()-1;j++){
            for(int i =j+n;i<s.length()+1;i++){
                if(isPalindrom(s.substring(j,i))){
                    System.out.println(s.substring(j,i));            
                }
            }
        }
    }
}

The complexity of the code I think is o(n^3). Please correct me if I am wrong. Somebody please confirm this is correct

Also can anybody tell me how to solve this problem using DP(Dynamic programming)?

v09
  • 840
  • 2
  • 12
  • 22
  • is the complexity n^3? – v09 Jul 31 '14 at 19:02
  • In your implementation, yes, looks like O(n^3). In practice, a bit less, probably, since those nested for loops are not O(n^2) but only (n*(n-1))/2, and the palindrome-check will fail early in most cases, but it's in the same ballpark. – tobias_k Jul 31 '14 at 19:06
  • thanks .. Any idea how to do it using DP? – v09 Jul 31 '14 at 19:25
  • Ehrm... have you read the answer from that "possible duplicate" comment? – tobias_k Jul 31 '14 at 19:28

0 Answers0