Q9. Algorithms STL#9
A student just learnt the reverse() function in c++ STL. He writes the following algorithm to check if a given string S is a palindrome.
bool isPalindrome(string& s)
string rev = s
reverse(rev.begin(), rev.end())
return s == rev
Is the algorithm correct? What is the space and time complexity?
No syntactical error but algorithm just does not work on all possible range of inputs.
Algorithm is correct and uses O(N) time and O(1) space.
Syntactical error, correction in statement 2 : rev = reverse(rev.begin(), rev.end())
Algorithm is correct and uses O(N) time and O(N) extra space.