Problem overview
The method reverse receives a String named input and returns the same characters in the opposite order. For "hello" the result is "olleh". The task is to do the work yourself, without calling a built-in reverse.
The statement allows O(n^2) time and O(n) extra space, where n is the length of the string. That is a generous budget, and it hints at the approach: build the answer by repeatedly joining strings, which is simple but copies text over and over.
Approach: put each new character in front
Start with an empty result. Walk through the input from the first character to the last. For each character, place it at the front of the result built so far.
For "abc" the result grows like this:
- Start:
"" - After
'a':"a" - After
'b':"ba", because'b'goes in front of"a" - After
'c':"cba"
The first character of the input ends up last, and the last ends up first, which is exactly a reversal.
The cost comes from how strings work. A String can't be modified, so joining one character to the front of a string of length k builds a new string and copies all k + 1 characters. Over the whole input that is 1 + 2 + ... + n copies, which is on the order of n^2. The space is O(n) because only the current result and one new string of at most n characters exist at a time. Other lessons on this problem reach a faster running time by changing the data structure; this one keeps to plain concatenation.
Step by step
- Declare the result as a
varholding an empty string. It is avarbecause the loop assigns a new string to it on every pass. - Loop over the characters of
inputwith aforcomprehension, naming the loop variablecharacter. AStringcan be used directly as a source ofCharvalues. - Prepend the character. Convert it with
toStringand put it before the current result, then store the new string back in the variable. - Return the result after the loop.
The solution in Scala
class Solution {
def reverse(input: String): String = {
var reversedString = ""
for (character <- input) {
reversedString = character.toString + reversedString
}
return reversedString
}
}
The Scala details worth knowing:
- Why
toString? The loop variable is aChar. ACharfollowed by+and a number is arithmetic:'x' + 1is theInt121. Converting the character to a one-letter string first makes+unambiguous, since the result is aStringeither way. - Looping over a string.
for (character <- input)visits the characters left to right, in order. No index is needed. - The input is never changed. Strings are immutable, so the loop reads
inputand builds a separate value. The caller's string stays as it was. returnis optional. The last expression of a block is the block's value, so ending the method with justreversedStringwould be equivalent.
Complexity
Time: O(n^2). The loop runs n times. Pass number k creates a string of length k, which costs about k character copies. The total is 1 + 2 + ... + n = n(n + 1) / 2 copies. This matches the bound in the statement, and for strings of a few thousand characters it is fast enough.
Space: O(n). The result reaches length n. Old intermediate strings become garbage as soon as the next one is built, so they don't add up.
Edge cases and common mistakes
- Empty string. The loop doesn't run and the method returns
"". - One character.
"a"comes back as"a". - Spaces and punctuation. They are characters like any other, so
"ab cd"becomes"dc ba". - Appending instead of prepending.
reversedString = reversedString + character.toStringrebuilds the original string unchanged. - Using a
val. The result is reassigned in the loop, so it must be avar. - Forgetting
toString. Writingcharacter + reversedStringcan work for aCharand aString, but the explicit conversion makes the intent clear and keeps the code from turning into numeric addition if the types change.
Testing
"hello"gives"olleh"."ab cd"gives"dc ba"."a"gives"a".""gives"".
