Valid Palindrome

Question

Problem is to check if the string is valid palindrome or not. Return true for empty strings.

What's the problem with my code? It is failing for the input "ab"

public class Solution {
    Boolean b;

    public Boolean isPalindrome(String s) {

        s = s.toLowerCase();
        s = s.replaceAll("[^a-zA-Z0-9]","");

        if(s.length()==1 || s.isEmpty())
        {
            return true;
        }

        for (int i=0;i<s.length()-1;i++)
        {
            b = expandAroundCenter(s,i,i+1);
            b = expandAroundCenter(s,i,i);
        }

        return b;
    }

    public Boolean expandAroundCenter(String s,int start,int end)
    {
        while(start>=0 && end<s.length() ) 
        {
            if ((s.charAt(start))!=(s.charAt(end)))
            {
                return false;
            }

            start--;
            end++;
        }
        return true;
    }
}

`It is failing for the input "ab"` , for sure it should since it's not what is expected to be — Traian GEICU, Jan 15 '21 at 01:51
What’s wrong with just reversing `s` and comparing that to `s`? Essentially, `reverse(s).equals(s)`? — Cole Tobin, Jan 15 '21 at 02:05

score 2 · Answer 1 · answered Jan 15 '21 at 02:02

You've got big logic flaws here.

Firstly, in your for loop you call expandAroundCenter twice, and overwrite the first results. Secondly, you're doing this in a for loop, and overwriting all previous results. Also I think you're making things harder than they need to be by starting in the middle. Start on the edges, and work inward!

Calculating a palindrome is a great opportunity for a recursive function (one that calls itself). I'll give you the pseudo-code, it's up to you to implement:

public Boolean IsPalindrome(string s)
    // If we are down to 1 or zero characters, success!
    // This deals nicely with odd numbered length strings
    if(length <= 1)
        return true;
    
    // If the first and last don't match, it's not a palindrome
    if(first letter != last letter)
        return false;
    
    // Since we know the first and last match, strip them off, then repeat
    return IsPalindrome(strip first and last letter from string)
}

score 1 · Answer 2 · answered Jan 15 '21 at 02:13

If there are no constraints, the best way to solve this problem is to use recursive.

class  palindrome 
{ 
    static boolean isPalRec(String str,  
                            int s, int e) 
    {  

        if(s == "")
            return true;
        if (s == e) 
            return true; 
  
        if ((str.charAt(s)) != (str.charAt(e))) 
            return false; 

        if (s < e + 1) 
            return isPalRec(str, s + 1, e - 1); 
  
        return true; 
    } 
  
    static boolean isPalindrome(String str) 
    { 
        int n = str.length(); 

        if (n == 0) 
            return true; 
  
        return isPalRec(str, 0, n - 1); 
    } 
  
}

Valid Palindrome

2 Answers2