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