alpenglow's blog

By alpenglow, history, 6 weeks ago, In English

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'.

 
 
 
 
  • Vote: I like it
  • +13
  • Vote: I do not like it

»
6 weeks ago, # |
Rev. 2   Vote: I like it +27 Vote: I do not like it

You can do also like that;

bool is_palindrome(std::string str) {
    return std::equal(str.begin(), str.end(), str.rbegin());
}
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Wow!

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

the Time Complexity of the first way is O(n / 2), the others if O(n).

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +36 Vote: I do not like it

    I hate to be that guy but $$$O(\frac{n}{2})$$$ is still $$$O(n)$$$

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Yes, as said, those time complexities are same, but I added the answer to this comment (about # of operations) to the blog.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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)$$$

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by alpenglow (previous revision, new revision, compare).