Reverse

Next, we will implement a reverse routine, a function which takes a String as an argument and returns a new String containing the characters of the argument in reverse.

   String
   reverse(String s)
   {
       String rslt;
       for(int i=length(s)-1;i>=0;i--)
           rslt += s.char_at(i);
       return rslt;
   }

Since the complexity of the += char operator is constant in general, this algorithm will be linear in the length of s. Notice that reverse could also have been implemented using the unget function as follows:

   String
   reverse(String s)
   {
       String rslt;
       for(int i=0;i<length(s);i++)
           rslt.unget(s.char_at(i));
       return rslt;
   }

However, the complexity of the prepend function, unget, is linear in the length of s; therefore the complexity of this reverse algorithm will be quadratic. Hint: Where possible, append instead of prepend.

Also, note that we use the char_at() function instead of operator[]() since we are just retrieving characters from the String. Hint: Use s.char_at(i) where possible instead of s[i].