everyone! I know that this is not the best possible base case for recursion, and I am aware that it has flaws. But, while working on it, I've realize that few times, it skips slicing the first element of the array, eventually returning the false instead of true.
I am probably missing something, but I would love to learn why is this happening?
PS. I apologize if this question might not be perfectly phrased, but I hope the code will give you some better idea.
The code:
function palindrome(string) {
let str = string.replace(/[^A-Za-z0-9]/g, '')
console.log( str )
str = str.split("")
if (str.length === 3 && str[0] === str[2] || str.length === 1) {
return true
} else if (str.length === 2 && str[0] !== str[1]) {
return false
} else {
return palindrome(string.slice(1, -1))
}
return false
}
console.log(palindrome("Anne I vote more cars race Rome to Vienna"))With the return value of:
['A', 'n', 'n', 'a', 'I', 'v', 'o', 't', 'e', 'm', 'o', 'r', 'e', 'c', 'a', 'r', 's', 'r', 'a', 'c', 'e', 'R', 'o', 'm', 'e', 't', 'o', 'V', 'i', 'e', 'n', 'n', 'a']
['n', 'n', 'a', 'I', 'v', 'o', 't', 'e', 'm', 'o', 'r', 'e', 'c', 'a', 'r', 's', 'r', 'a', 'c', 'e', 'R', 'o', 'm', 'e', 't', 'o', 'V', 'i', 'e', 'n', 'n']
['n', 'a', 'I', 'v', 'o', 't', 'e', 'm', 'o', 'r', 'e', 'c', 'a', 'r', 's', 'r', 'a', 'c', 'e', 'R', 'o', 'm', 'e', 't', 'o', 'V', 'i', 'e', 'n']
['a', 'I', 'v', 'o', 't', 'e', 'm', 'o', 'r', 'e', 'c', 'a', 'r', 's', 'r', 'a', 'c', 'e', 'R', 'o', 'm', 'e', 't', 'o', 'V', 'i', 'e']
['I', 'v', 'o', 't', 'e', 'm', 'o', 'r', 'e', 'c', 'a', 'r', 's', 'r', 'a', 'c', 'e', 'R', 'o', 'm', 'e', 't', 'o', 'V', 'i']
['I', 'v', 'o', 't', 'e', 'm', 'o', 'r', 'e', 'c', 'a', 'r', 's', 'r', 'a', 'c', 'e', 'R', 'o', 'm', 'e', 't', 'o', 'V']
['I', 'v', 'o', 't', 'e', 'm', 'o', 'r', 'e', 'c', 'a', 'r', 's', 'r', 'a', 'c', 'e', 'R', 'o', 'm', 'e', 't', 'o']
['v', 'o', 't', 'e', 'm', 'o', 'r', 'e', 'c', 'a', 'r', 's', 'r', 'a', 'c', 'e', 'R', 'o', 'm', 'e', 't', 'o']
['v', 'o', 't', 'e', 'm', 'o', 'r', 'e', 'c', 'a', 'r', 's', 'r', 'a', 'c', 'e', 'R', 'o', 'm', 'e', 't']
['o', 't', 'e', 'm', 'o', 'r', 'e', 'c', 'a', 'r', 's', 'r', 'a', 'c', 'e', 'R', 'o', 'm', 'e']
['t', 'e', 'm', 'o', 'r', 'e', 'c', 'a', 'r', 's', 'r', 'a', 'c', 'e', 'R', 'o', 'm', 'e']
['e', 'm', 'o', 'r', 'e', 'c', 'a', 'r', 's', 'r', 'a', 'c', 'e', 'R', 'o', 'm']
['m', 'o', 'r', 'e', 'c', 'a', 'r', 's', 'r', 'a', 'c', 'e', 'R', 'o']
['m', 'o', 'r', 'e', 'c', 'a', 'r', 's', 'r', 'a', 'c', 'e', 'R']
['o', 'r', 'e', 'c', 'a', 'r', 's', 'r', 'a', 'c', 'e']
['r', 'e', 'c', 'a', 'r', 's', 'r', 'a', 'c', 'e']
['e', 'c', 'a', 'r', 's', 'r', 'a', 'c']
['c', 'a', 'r', 's', 'r', 'a']
['c', 'a', 'r', 's', 'r']
['a', 'r', 's']
['r', 's']
false
CodePudding user response：
You do the .slice(1, -1) on the wrong element because it keeps the spaces and these do not match in the palindrome.
And your code just tests the last letters in the center, and forgets all the others around.
I'd rather see the code this way
console.log(palindrome("Anne I vote more cars race Rome to Vienna"))
function palindrome( str )
{
return recussiv( str.replace(/[^A-Za-z0-9]/g, '').toLowerCase() )
function recussiv(s)
{
console.log('-->', s )
if (s.length > 1)
{
return (s[0] === s[s.length-1]) ? recussiv(s.slice(1, -1)) : false
}
else return true
}
}.as-console-wrapper { max-height: 100% !important; top: 0CodePudding user response：
Problems with implementation
I'm afraid there are at least three separate problems with this implementation.
First, it forgets to same-case the characters, and the initial capital 'A' from 'Anne' won't match the final lower-case 'a' from 'Vienna'.
Second, it properly alters the string input to remove non-alphanumeric characters, but then when it recurs, it does so on this original string rather than on the new str.
Third, and most fundamentally, it doesn't check the most important fact before it recurs: it doesn't test whether the first character matches the last character.
Getting initial version working
We can fix all those and get a version that looks like this:
function palindrome(string) {
let str = string.replace(/[^A-Za-z0-9]/g, '') .toLowerCase ().split("") // Issue 1 -- case
// console.log( str.join('') )
if (str.length === 3 && str[0] === str[2] || str.length === 1) {
return true
} else if (str.length === 2 && str[0] !== str[1]) { // Issue 3 -- compare first and last
return false
} else if (str [0] !== str [str .length - 1]) {
return false
} else {
return palindrome(str.slice(1, -1).join('')) // Issue 2 -- recur on correct item
}
return false
}
console .log (palindrome ("Anne I vote more cars race Rome to Vienna")) //=> true
console .log (palindrome ("Anne I vote more cars X race Rome to Vienna")) //=> false
console .log (palindrome ("A man, a plan, a canal: Panama!")) //=> true
console .log (palindrome ("A man, a plan, a banal palindrome.")) //=> falseRemaining problems
But even here, there is some real ugliness. We convert back and forth between strings and arrays on every call. We run the string clean-up on every call, when it shouldn't be needed after the first one. And it contains many more separate cases than are really necessary.
Don't keep converting
The first fix is trivial. We simply don't need arrays here. We can do all our tests on strings. The characters in a string can be indexed exactly like array items, and they have an equivalent length property.
Initialize only once
The second issue, that of rerunning the initialization on each call is usually fixed in one of two ways: adding extra parameters which are defaulted on the initial call, or adding a helper functions. We'll choose the latter because there are some real potential problems with the former (although it's often enough still worth considering.) This breaks down into two styles. We can nest the helper function inside our main function and then call it from inside. Or we can make it an external function that we just call. The answer from MisterJoJo aptly demonstrates the first style, so we can look at the second. Here we can write an internal recursive _isPalindrome function that takes a string of lower-case alphanumeric characters and returns a boolean. And then we could write a public wrapper function that accepts any string, normalizes it by removing all non-alphanumeric characters and lower-casing it, passing the result to that internal function and returning its result. It might look something like this1:
const isPalindrome = (string) =>
_isPalindrome (string .replace (/\W/g, '') .toLowerCase())
const _isPalindrome = (cs) => /* ... recursive version here ... */
In these days of easy-to-use JS modules, that internal function can be encapsulated in the module, leaving only the main function publicly visible.
Handle fewer cases
For the third issue, we need to really look at what it means to be a palindrome. Fundamentally, it simply means that the string reads the same forward and backward. The intuition represented by this answer is that this means that the first and last characters are the same and the remaining string between them is also a palindrome.
For a recursive function, we need at least one base case. When can we no longer check whether the first and last character are the same? The answer is pretty clearly: when we don't have separate first and last characters.2. So our base case is when there's zero or one characters in a string. A one-character string is clearly a palindrome. So is a zero-character string; if this sounds odd, please look up vacuous truths. So we now have a simple base case, and a simple recursive case, and we can just write our function:
const isPalindrome = (string) =>
_isPalindrome (string .replace (/\W/g, '') .toLowerCase ())
const _isPalindrome = (cs) =>
cs .length < 2
? true
: cs [0] == cs [cs .length - 1] && _isPalindrome (cs .slice (1, -1))
console .log (isPalindrome ("Anne I vote more cars race Rome to Vienna")) //=> true
console .log (isPalindrome ("Anne I vote more cars X race Rome to Vienna")) //=> false
console .log (isPalindrome ("A man, a plan, a canal: Panama!")) //=> true
console .log (isPalindrome ("A man, a plan, a banal palindrome.")) //=> falseUsing utility functions
We could easily stop here. But there is still some ugliness in that code. All the index manipulations take some reading to understand. There is a strong argument to move that ugliness into well-named helper functions. I usually have laying around the helpers last and first3, and it's easy enough to also write a middle. These take the first or last characters of a string or array, or, for middle, take everything between the first and last characters. Using those can make our main function more readable:
const first = (xs) => xs [0]
const last = (xs) => xs [xs .length - 1]
const middle = (xs) => xs .slice (1, -1)
const isPalindrome = (string) =>
_isPalindrome (string .replace (/\W/g, '') .toLowerCase ())
const _isPalindrome = (cs) =>
cs .length < 2
? true
: first (cs) == last (cs) && _isPalindrome (middle (cs))
Generic processing
We accidentally wrote a more generic version of the function than we were trying to write! Note that we can use this same internal function on arrays:
_isPalindrome (['foo', 'bar', 'qux', 'bar', 'foo']) //=> true
_isPalindrome (['foo', 'bar', 'qux', 'foo']) //=> false
The semantics are simple. An array is a palindrome if it has fewer than two elements or if the first and last element are the same and the remaining elements form a palindrome.
This was mostly a happy accident. When I noticed it, I changed the parameter name that I originally wrote, letters to the more generic cs, which just might bring to mind characters but doesn't insist on it.
Noting the generic nature of this implementation, I would probably change middle so that we could carry this to even more types, to any finite iterable type. middle won't handle this right now because not all such iterables have slice methods. But all of them4 can be converted arrays, and then we can use the array slice method.
Here is a simple update to middle to make this function still more generic:
const middle = (xs) => [...xs] .slice (1, -1)
As I said, this was a happy accident. I didn't notice it while writing the code, only while typing up this post.
Much simpler isPalindrome
Finally, the question noted that this problem is probably not best solved with recursion. That's quite true. We glossed by it before, but did mention that a string is a palindrome if it reads the same forward and backward. We can write that directly:
const isPalindrome = (string) =>
_isPalindrome (string .replace (/\W/g, '') .toLowerCase ())
const _isPalindrome = (s) =>
s == s .split ('') .reverse () .join ('')
console .log (isPalindrome ("Anne I vote more cars race Rome to Vienna")) //=> true
console .log (isPalindrome ("Anne I vote more cars X race Rome to Vienna")) //=> false
console .log (isPalindrome ("A man, a plan, a canal: Panama!")) //=> true
console .log (isPalindrome ("A man, a plan, a banal palindrome.")) //=> falseWhile String does not have a reverse method, we can easily convert to an array, reverse the array, and join the result back into a string. Then we simply test whether the reversed string is the same as the original.5
This version is not generic like the last one, but it is definitely a more direct translation of the idea of a palindrome directly into code.
1 Note that the regular expression /\W/g is precisely equivalent to /[^A-Za-z0-9]/g. It's the converse of \w, which represents [a-zA-z0-9], but is simpler to type.
2 We can also note that if the first and last characters are the same, that is, if our string is only one character long, we could use the same process. All that would change is whether we test for length less than 2 or less than 1.
3 first is often called head for reasons not worth discussing here.
4 Well, again, the finite ones
5 It's probably worth extracting a reverseString helper function from this, for the same reason we did first and last above. It's a genuinely reusable simple function. That's left as an exercise.