CODEWITHSUNDEEP
java
mohamed mohsen
mohamed mohsen

Reputation: 13

recursive method that checks if a string is palindrome in java

the input: "mnkknm" where n=0 the output: flag is always equal 1 while it should be equal 3 and it returns -1 what is the problem ? note : palindrome means for example if the Reverse of malayalam is also malayalam then its palindrome another note : i should write the code recursive as it's a homework

public static int PalindromeCheck(String x , int n) 
{

int flag =0;
if (n+1 !=x.length()/2)
{
char s = x.charAt(n);
char y = x.charAt(x.length()-1-n);
if (s==y)
{    flag++;
System.out.println(flag); // i write it to check the value of the flag
}

return  flag+PalindromeCheck(x,n+1) ;
}

if (flag==x.length()/2)
{
return 1;}
else{
return -1;
}

Upvotes: 0

Views: 416

Answers (3)

RARE Kpop Manifesto
RARE Kpop Manifesto

Reputation: 2915

i'd first do 2 or 3 quick checks :

  1. if first character fail to match the last. that's a huge time saver without having to reverse anything, esp when input is really long

  2. then ask it to locate any character that isn't the same as the first. if not, the string already is a nonstop-chain of that same character, then it must be a palindrome.

  3. (optional one) if input is REALLY REALLY long, quick check on distribution of components of just that same first character - by definition of a palindrome,

if length is even then # of occurrences of that char must also be even.

if length is odd, then it should be even unless the exactly-center character is also that same one, otherwise you'll know the distribution is already not-balanced between left and right, then what's the point of reversing it when u can return false at this point and save time.

if both passes, then do what others have suggested : reverse the right-side half and check if it lines up with left-most index position (0 or 1 depending on which langauge). The reversal part doesn't have to do any of these small checks. just reverse it at high speed.

Upvotes: 0

TanvirChowdhury
TanvirChowdhury

Reputation: 2445

try this method please 

public static boolean isPal(String s)
{
    if(s.length() == 0 || s.length() == 1) {
        return true;
    }
    if(s.charAt(0) == s.charAt(s.length()-1)) {

        return isPal(s.substring(1, s.length() - 1));
    }
    return false;
}

Upvotes: 1

Elliott Frisch
Elliott Frisch

Reputation: 201537

First, I would create a helped method with that recursive signature (the public function should just take a String). And we can test for null and the empty string as special cases there. Like,

public static boolean isPalindrome(String x) {
    if (x == null) {
        return false;
    } else if (x.isEmpty()) {
        return true;
    }
    return isPalindrome(x, 0);
}

Then your current method seems close, but you want to compare n with a less than operator to the half of the length of x. Then test that the character matches on the right hand side (offset by n from x.length() but we need a -1 because of zero based indexing). Also, the method should return a boolean (and I fixed the name). Like

private static boolean isPalindrome(String x, int n) {
    if (n < x.length() / 2) {
        if (x.charAt(n) != x.charAt(x.length() - n - 1)) {
            return false;
        }
        return isPalindrome(x, n + 1);
    }
    return true;
}

Upvotes: 1

Related Questions