Problem overview
The method reverse(_ input: String) -> String returns the characters of input in the opposite order: "hello" becomes "olleh". This lesson asks for O(n) time and O(n) extra space.
Approach: read backwards, append forwards
The simple way to reverse is to prepend each character to the result, but that copies the growing result every time and takes O(n²). The faster way flips the roles: visit the input from the last character to the first, and append each one to the end of the result. Appending to the end of a Swift string takes amortized constant time, so the whole loop is linear.
There is one obstacle. A Swift string cannot be indexed by integer, so you cannot ask for "the character at position i". The fix is to copy the characters into an array once, in O(n), and index the array.
Step by step
- Prepare the result and the array.
reversedStringis avarholding"".charactersis aletset toArray(input), a[Character]that can be indexed. - Loop backwards over the indexes. The indexes run from
characters.count - 1down to 0, so usestride(from: characters.count - 1, through: 0, by: -1).through:includes 0, whileto:would stop before it and lose the first character. - Append. Add
String(characters[i])to the end ofreversedStringwith+=. The element is aCharacter, so it is converted to aStringfirst. - Return the result.
The solution in Swift
class Solution {
func reverse(_ input: String) -> String {
var reversedString = ""
let characters = Array(input)
for i in stride(from: characters.count - 1, through: 0, by: -1) {
reversedString += String(characters[i])
}
return reversedString
}
}
The Swift details worth a closer look:
- Counting down. Swift's range syntax only goes upward:
5...0stops the program, because a range cannot end below its start.strideaccepts a negative step, so it is the tool for counting down. - The empty string. Then
characters.count - 1is -1, and a stride from -1 through 0 with step -1 is empty. The loop does not run and the method returns"". - No overflow worry. The index
iis a plainInt, which can hold -1, unlike an unsigned type. Counting down never goes wrong at 0. - Characters stay whole. Each array element is one
Character, so a letter with a combining accent keeps its accent when the order is reversed. - The array is a copy. Changing the array would not change
input, and this method only reads it.
Complexity
Time: O(n). Building the array visits each character once. The loop runs n times, and each append takes amortized constant time. The total is linear.
Space: O(n). The array holds n characters and the result holds another n. Constants aside, the extra memory grows with the input.
Edge cases and common mistakes
- Starting at
characters.count. The last valid index iscount - 1. Starting one higher reads past the end of the array and stops the program. - Using
to:instead ofthrough:. The stride then stops before 0, and the first character of the input is missing from the result. - Appending
characters[i]withoutString(...). ACharactercannot be added to aStringwith+=; the compiler reports an error. - Trying
input[i]. Strings have no integer subscript, which is why the array exists.
Testing
"hello"gives"olleh".""gives""."a"gives"a"."ab"gives"ba"."ab cd"gives"dc ba".
