### alpenglow's blog

By alpenglow, history, 6 weeks ago, In C++ let's check if the string is palindrome in 3 different ways:

#1 Longer code, but efficient way
#2 Little bit shorter code, but not so efficient way
#3 The shortest code, but not so efficient way

I declared the first one as the most efficient, because it does not create a new string, but anyways, after the function is end, it must get deleted from the memory. So you can use the last one if you are not very limited in memory.

UPD Adding the 4-th way suggested by Halit and this is the best possible way.

#4 The shortest code and efficient way

You can find info about that last one here.

UPD2 Time complexity was mentioned in the comments. The time complexity is $O(n)$ for all of those 4 ways. But some of them is at most $n/2$ operations (comparisons of chars) and some $n$. If you care about that, you can use the last approach, because I can not modify that 3-rd approach to make it $n/2$ operations, because getting substring can not be done in $O(1)$ in C++ unlike Java.

UPD3 Notice from the 3-rd way when you want to reverse string and keep the original one as well, doing string t(s.rbegin(), s.rend()) is better than doing string t = s and then reverse(t.begin(), t.end()). Also when you want to print reversed directly, you can do cout << string(s.rbegin(), s.rend()) << '\n'. Comments (10)
 » 6 weeks ago, # | ← Rev. 2 →   You can do also like that; bool is_palindrome(std::string str) { return std::equal(str.begin(), str.end(), str.rbegin()); } 
•  » » Wow, this is probably the best way. I think it does not create a new string?
•  » » » yes, it doesn't create a new string. https://en.cppreference.com/w/cpp/algorithm/equal
 » Wow!
 » the Time Complexity of the first way is O(n / 2), the others if O(n).
•  » » I hate to be that guy but $O(\frac{n}{2})$ is still $O(n)$
•  » » Yes, as said, those time complexities are same, but I added the answer to this comment (about # of operations) to the blog.
 » I guess you can also do a polynomial rolling hash for the string and check it that way. The string hashing is completely necessary and totally can't be substituted for naive character by character comparison. Time complexity is $O(n)$
•  » » It is an overkill for a full string check, but efficient for checking many different substrings. So, hashing can solve the longest palindromic substring problem by also using binary search the answer technique.
 » Auto comment: topic has been updated by alpenglow (previous revision, new revision, compare).