Problem overview
The method reverse receives a string, input, and returns a new string with the characters in the opposite order. For "hello" it returns "olleh". The lesson asks for O(n) time and O(n) extra space, and for a solution that does the reversing itself instead of calling a ready-made reversal.
Approach: swap the ends and walk inward
Reversing a sequence means that the first element trades places with the last, the second with the second to last, and so on. Two pointers do this: left starts at the first position and right at the last. Swap the two characters, move left one step right and right one step left, and repeat until the pointers meet or cross.
When the length is odd, the pointers meet on the middle character, which stays where it is. When the length is even, they cross after the last swap. In both cases the loop condition left < right stops at the right moment.
Swift strings can't be changed by position, and they can't even be read by an integer index. So the method first copies the characters into an array, reverses the array in place, and builds a new string from it. The copy is why the space is O(n).
Step by step
- Copy the characters.
var charArray = Array(input)gives a[Character]with one element per character. It is avar, because the swaps will change it. - Create
leftas avarstarting at 0. - Create
rightas avarstarting at the last index,charArray.count - 1. - Loop while
left < right. Once they meet or cross, every pair has been swapped. - Call
self.swap(&charArray, left, right)inside the loop. The method is written in the next steps. The&passes the array as aninoutargument, which lets the method change the caller's array. - Declare the helper above
reverseasfunc swap(_ arr: inout [Character], _ i: Int, _ j: Int).inoutmeans the function may change the caller's variable. The underscores let callers pass the arguments without names. - Write its body with a temporary. Save
arr[i]in the constantc, copyarr[j]intoarr[i], then putcintoarr[j]. Without the temporary, the first assignment would destroy a value before it was copied. - Move the pointers after the swap with
left += 1andright -= 1. - Return
String(charArray), which builds a string from the characters.
The solution in Swift
class Solution {
func swap(_ arr: inout [Character], _ i: Int, _ j: Int) {
let c = arr[i]
arr[i] = arr[j]
arr[j] = c
}
func reverse(_ input: String) -> String {
var charArray = Array(input)
var left = 0
var right = charArray.count - 1
while left < right {
self.swap(&charArray, left, right)
left += 1
right -= 1
}
return String(charArray)
}
}
Swift details worth knowing:
inoutand&. Swift passes arrays by value: a function normally gets its own logical copy. Marking a parameterinoutand writing&at the call tells Swift to write the changed array back into the caller's variable when the function returns. Withoutinout, the assignmentarr[i] = ...would not compile, because parameters are constants.- The name
swap. The standard library already has a global functionswap. Inside a class, an unqualifiedswap(...)refers to the class's own method first. Writingself.swap(...)makes it clear which one is meant. Calling the global one inside this class needs the prefixSwift.swap, or the compiler reports thatswaprefers to the instance method. - Characters, not bytes.
Array(input)splits the string byCharacter, one user-visible character each. A letter plus a combining accent, or a flag emoji, is one element, so reversing the array never separates the parts. For example"ab🇺🇸c"becomes"c🇺🇸ba", with the flag intact. - Value semantics. If
b = afor two arrays and you changeb,ais unchanged. The method reverses its owncharArrayand never touches the caller's string, which is immutable anyway. - The
Stringinitializer.String(charArray)accepts any sequence of characters.
Swift also offers shorter ways to reverse, such as String(input.reversed()) or swapAt(_:_:) on an array. Both give the same results on these inputs, and this lesson writes the swap by hand to practise pointers and inout.
Complexity
Time: O(n). Copying into the array, the loop of about n / 2 swaps, and building the result string each take linear time.
Space: O(n). The character array and the result string each hold n characters. The pointers and the temporary add only O(1).
Edge cases and common mistakes
- Empty string.
rightis -1 and the loop doesn't run, so the method returns"". - One character.
leftandrightare both 0, the condition fails, and"a"comes back unchanged. - Odd and even lengths.
"abc"gives"cba", with thebuntouched, and"ab"gives"ba". - Looping to the end. If the loop ran until
leftreached the last index, each pair would be swapped twice and the string would come back unchanged. - Forgetting
&. PassingcharArrayto aninoutparameter without the ampersand is a compile error. - Swapping without a temporary. Writing
arr[i] = arr[j]followed byarr[j] = arr[i]leaves both positions with the same character. - Forgetting to move the pointers. The loop would swap the same pair forever.
Testing
"hello"gives"olleh".""gives""."a"gives"a"."ab"gives"ba"."abc"gives"cba".
