- Joined
- Aug 7, 2013
- Messages
- 1,338
Hi,
What is the best method, time complexity wise, to detect if a string is a palindrome, e.g.
The algorithm I got is to simply check off each character with the string in place, e.g. compare the 0th and nth character, then the 1th and n - 1 th character, etc. If any do not match, then reject and return false. Otherwise return true.
This algorithm is also found on stack overflow.com: http://stackoverflow.com/questions/8444710/easiest-way-to-check-if-a-string-is-palindrome
This is O(n) because its linear with respect to the size of the palindrome.
Is there anyway to do this check faster than linear time? If not, can someone show a (mathematical) proof that the Palindrome Acceptance Problem cannot be done faster than O(n)?
What is the best method, time complexity wise, to detect if a string is a palindrome, e.g.
Code:
function isPalindrome takes string whichString returns boolean
…
endfunctionThe algorithm I got is to simply check off each character with the string in place, e.g. compare the 0th and nth character, then the 1th and n - 1 th character, etc. If any do not match, then reject and return false. Otherwise return true.
This algorithm is also found on stack overflow.com: http://stackoverflow.com/questions/8444710/easiest-way-to-check-if-a-string-is-palindrome
This is O(n) because its linear with respect to the size of the palindrome.
Is there anyway to do this check faster than linear time? If not, can someone show a (mathematical) proof that the Palindrome Acceptance Problem cannot be done faster than O(n)?
