Problem overview
The method reverse(_ input: String) -> String returns the characters of input in the opposite order. For "hello" the result is "olleh". The lesson asks for O(n²) time and O(n) extra space, which tells you which approach to write: build the answer by putting each new character in front of the ones already collected.
Approach: prepend each character
Walk through the input from left to right and keep a result string. If every character you read is placed at the front of the result, the first character ends up last and the last one ends up first:
read h -> h
read e -> eh
read l -> leh
read l -> lleh
read o -> olleh
This is simple, because the loop needs no indexes. The price is time. A Swift String is a value that cannot be edited at its front, so "prepend" builds a brand new string by copying the characters that were already collected. The k-th step copies about k characters, and 1 + 2 + ... + n is about n²/2, so the whole loop is O(n²). The next lesson on this problem appends to the end instead and gets O(n).
Step by step
- Start with an empty result. Declare
reversedStringwithvar, because the loop reassigns it, and set it to"". - Loop over the input. A
for-in loop over a string visits its characters in order. Name the loop variablecharacter. - Prepend. Assign
String(character) + reversedStringback toreversedString. The loop variable is aCharacter, and+does not join aCharacterwith aString, so it is converted withString(...)first. - Return the result after the loop.
The solution in Swift
class Solution {
func reverse(_ input: String) -> String {
var reversedString = ""
for character in input {
reversedString = String(character) + reversedString
}
return reversedString
}
}
The Swift details worth a closer look:
- Characters, not bytes. The loop visits
Charactervalues, each one a single visible character. A letter with a combining accent, such as "e" followed by U+0301, is oneCharacter, so it stays together and keeps its accent after the reversal. Reversing raw bytes would break it. - Why
String(character). Without the conversion the compiler reports that it cannot convert a value of typeCharacterto the expected argument typeString. - Value semantics. The method never changes
input. Parameters are constants, and strings are copied on assignment, so the caller's string is untouched. - The empty string. The loop body never runs and the method returns
"".
Complexity
Time: O(n²). Each of the n iterations creates a new string whose length is the number of characters read so far, and the copying adds up to about n²/2 character moves. Running the method on inputs of 20,000 and 80,000 characters shows the effect: four times the input takes roughly ten times as long.
Space: O(n). The result holds n characters. Each intermediate string is dropped when the next one replaces it, so only a constant number of them exist at once.
Edge cases and common mistakes
- Appending instead of prepending.
reversedString += String(character)rebuilds the original string, so"hello"stays"hello". - Using
let.reversedStringis reassigned in the loop, so it must be avar. The compiler rejects an assignment to a constant. - A single character.
"a"comes back as"a", and"ab"as"ba". - Spaces and punctuation. They are characters like any other:
"ab cd"becomes"dc ba".
Testing
"hello"gives"olleh".""gives""."a"gives"a"."ab"gives"ba"."ab cd"gives"dc ba".
