Algorithm STL Quiz Question

#1

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?

a. No syntactical error but algorithm just does not work on all possible range of inputs.

b. Algorithm is correct and uses O(N) time and O(1) space.

c. Syntactical error, correction in statement 2 : rev = reverse(rev.begin(), rev.end())

d. Algorithm is correct and uses O(N) time and O(N) extra space.

#2

answer d hoga na .

kyunki rev (extra space) use kar rahe hai.
jiska size s (n) ke size pe depend karega isliye O(n) space.

O(n) time complexity qunki constructor O(n) time lega s ko rev mein copy karne mein.
aur reverse function bhi O(n) lega reverse karne mein.
islye time complexity bhi O(n) ho jayegi

#3

Bhaiya, meh option b and d confuse tha.
Kyunki, “rev” hai toh single variable so I thought, tab space O(1) hona chahiye.

#4

string ko hamesha character array treat kiya karo time complexity nikalte time

2 Likes