Palindrome check
A string is a row of characters, indexed just like an array. To test whether it reads the same backwards, compare the first letter with the last, then step both inwards. One mismatch settles it.
racecar
Does "racecar" read the same backwards? Press play or step forward to start.
1function isPalindrome(s) {2 let lo = 0, hi = s.length - 1;3 while (lo < hi) {4 if (s[lo] !== s[hi]) return false;5 lo++; hi--;6 }7 return true;8}Keys: Space play or pause, ← → step. The URL always points at the frame you are on.
What it costs
| Case | Time | When |
|---|---|---|
| best | 1 | the first and last letters differ |
| average | n | a palindrome needs n / 2 checks |
| worst | n | a palindrome, or a mismatch in the middle |
| space | 1 | two indexes, no reversed copy |
Where it breaks
- Building the reversed string.
s === reverse(s)is shorter to write, but it copies all n letters before comparing any. The pointer version needs no copy and can stop at the first difference. - Even and odd lengths. Pick noon and racecar: with
lo < hi, the pointers cross on an even length and meet on the middle letter of an odd one. The middle letter never needs checking. - Real text. "Never odd or even" is a palindrome only once spaces and capitals are ignored. Real checks skip non-letters and compare lowercased characters.