Feedback request. Palindrome checker

JavaScript
#1

Link to the challenge

Just managed to implement working solution. Any feedback would be great. Also have question about… test cases i guess. The question will be under solution.

function palindrome(str) {

  /*formatting input
    1st step - get rid of non-alphanumeric char-s using regexp
    2nd step - avoid case sensitivity-related problems
  */
  let nonAlphaNumeric = /(_)*(\W)*/g;
  let formattedStr = str.replace(nonAlphaNumeric, '');
  formattedStr = formattedStr.toLowerCase();

  //Recursion

  //base case => empty string or 1-char string obviously palindrome
  if (formattedStr == '' || formattedStr.length == 1) {
    return true;
  }
  /*recursive step
  assume we have formattedStr => "abba"
  assume we've already checked all formattedStr except first and last character:
  that means we already know that 'bb' is palindrome
  'bb' in general case can be expressed => formattedStr.slice(1,-1)
  
  to check if 'abba' is palindrome we also need to ensure
  that 'a'=='a', in general case => 
  =>formattedStr[0] == formattedStr[formattedStr.length - 1]
  */
  else {
    return palindrome(formattedStr.slice(1,-1)) &&
           formattedStr[0] == formattedStr[formattedStr.length - 1];
  
  }
}

So my question is about specific cases like this(all input consists of special symbols):

console.log(palindrome("?!??<"));//my solution returns true
console.log(palindrome("..!!.."));//my solution returns true

There is no such cases in the challenge tests.
So idea of the challenge is that we ignore any special symbols no matter what?
Or maybe function should have some specific checks for such instances and return false?

#2

There’s couple test cases including non-alphanumeric characters. If those characters would be taken under consideration, these test cases would not pass.

Take a look at this part:

    return palindrome(formattedStr.slice(1,-1)) &&
           formattedStr[0] == formattedStr[formattedStr.length - 1];

Generally intent here is good, there’s though one detail here. Consider what happens when string has different first and last letter, but otherwise the corresponding letters taken from beginning and end are matching. You might consider whole function and sort of walk through the execution, for some case matching that requirement.

1 Like
#3

You are talking about cases such as below? Just making sure because my english isn’t ideal.

"accccb"
"1ddd2"
#4

Could you give us a specific example of what you are referring to?

#5

Yeah, for example "accccb" or similar string, starting with "a" and ending with "b", but with 50 "c"s in the middle.

#6

Just executed in Python tutor:

console.log(palindrome('acccb'));//false
console.log(palindrome('2bb3'));//false

Didn’t see any unexpected behavior, output is also as it should be.
Basically at the end of execution for ‘acccb’ we have

palindrome(formattedStr.slice(1,-1))//true for 'ccc'
formattedStr[0] == formattedStr[formattedStr.length - 1]//false  for 'a' and 'b'

So we have situation

true && false// return false
#7

Answer will be correct, yes. I’m trying to hint something else. I suggested using longer string, as the issue kind of exposes itself more in such case. Consider longer string, maybe even ridiculously long. First and last letter are different, the letters in the middle are the same. What function needs to do to come to conclusion that such string isn’t a palindrome?

#8

Well, for now I’m not sure what is the issue. You refer to the bigger size of input, so my suspicion is that it could be optimized, but I need more skills/knowledge to do it. Or maybe it’s about big O notation and efficiency? I’m eager to look into it, if you can provide some useful links that would be cool.

#9

You already have the knowledge to change that, I can assure you. Maybe try to think how you’d by hand check if some long string is palindrome. How that would be different from the function? What in function would need to be modified to make it more similar, specifically in the code pointed before?

#10

Oh… should i switch places two parts of expression? Check for first and last symbol should be BEFORE && operator?

#11

Yes! That makes function return false at the first occurrence of mismatching letters, instead of going all the way into recursive calls.

#12

I didn’t give enough attention to structure of expression(was too excited about ‘how do i implement recursive step’). Thanks for the discussion!

#13

That understandable, the point when everything is working is great one to take look and see whether something couldn’t be simplified or changed.

#14

So if I will try to generalize this case and will say:
'In situations:

<expression1>&&<expression2>

expression1 should be more simple check’, I will be correct? Can I use such concept as a rule? Or there are some hidden issues with this?

Also for situations like

<expression1>||<expression2>

order is not really important??? Program will need to check both expressions anyway, as I understand.

And finally, some time ago I was told that mathematical logic is useful for coding, and now such advice makes more and more sense. What do you think about that?

#15

It applies to both cases really, but in a way due to opposite reason.

For:

expression1 && expression2

If expression1 is false, the expression2 won’t be even evaluated. As regardless if expression2 is true or false, the result will be false:

false && false  # false
false && true  # false

On the other hand, for:

expression1 || expression2

If expression1 is true, then expression2 isn’t checked. The result will always be true.

true || true  # true
true || false  # true