Problem overview
The method reverseWords receives a string, input, made of words separated by a single space. It returns a string with the same words in reverse order, still separated by single spaces. A word is any run of non-space characters, and each word keeps its own spelling.
For "sky is blue" the answer is "blue is sky". The order of the three words flips, but blue is still spelled blue, not eulb.
Approach: reverse everything, then reverse each word
You could split the string into words, reverse that list and join it again. This lesson uses a different idea that works on the characters themselves, with only two-pointer swaps.
Take the whole string and reverse it. The words land in the opposite order, which is what we want, but each word is now spelled backwards:
sky is blue becomes eulb si yksReversing each word on its own puts its letters back in the right order. eulb turns into blue, si into is and yks into sky, and the spaces stay where they are. Two reversals of the same stretch of characters cancel each other, and that is why the trick works.
Reversing a range uses two indices that start at its ends and move toward each other, swapping the characters they point at until they meet.
Step by step
- Copy the characters into an array. A Swift
Stringcan't be indexed with an integer, so the code makesarrwithArray(input). It is avarbecause the algorithm changes it. - Reverse the whole array with a helper called
reverse, from index 0 toarr.count - 1. The array is passed with&because the helper modifies it. - Keep a start index
ifor the current word, and loop whileiis inside the array. - Find the end of the word. A second index
jstarts atiand moves right while it is inside the array andarr[j]isn't a space. The bounds check comes first, soarr[j]is never read past the end. - Reverse the word. When the inner loop stops, the word occupies
itoj - 1. Reversing that range fixes its spelling. - Jump to the next word by setting
itoj + 1, which skips the space. - Convert back with
String(arr)and return it. - Write
reverse. It takes the array asinoutplus the two indices and swaps whilei < j, movingiup andjdown after each swap. - Write
swap. It savesarr[i]intemp, copiesarr[j]intoarr[i], then putstempinarr[j].
The solution in Swift
class Solution {
func swap(_ arr: inout [Character], _ i: Int, _ j: Int) {
let temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
}
func reverse(_ arr: inout [Character], _ i: Int, _ j: Int) {
var i = i
var j = j
while i < j {
self.swap(&arr, i, j)
i += 1
j -= 1
}
}
func reverseWords(_ input: String) -> String {
var arr = Array(input)
self.reverse(&arr, 0, arr.count - 1)
var i = 0
while i < arr.count {
var j = i
while j < arr.count && arr[j] != " " {
j += 1
}
self.reverse(&arr, i, j - 1)
i = j + 1
}
return String(arr)
}
}
Swift details worth knowing:
inoutparameters. Function parameters are constants, so a plain array parameter couldn't be modified. Marking itinoutlets the helper change the caller's array, and the caller must pass it as&arr.- Shadowing
iandj. Those parameters are constants too, sovar i = icreates a mutable local copy with the same name. The caller's variables are not affected. self.swap. Swift's standard library already has a global function calledswap. Writingself.swapmakes it clear that the class's own method is meant.- Characters, not bytes.
Array(input)gives a[Character], and eachCharacteris one user-visible character. A letter followed by a combining accent counts as one element, so reversing the array never separates an accent from its letter. For example,"cafe\u{301} au lait"becomes"lait au café", with the accent still on thee. - No
++. Swift has no increment operator, so the code uses+= 1and-= 1.
Complexity
Time: O(n). The full reversal touches each character once. The word loop moves j over every character once in total, and reversing the words touches each character at most once more. The work is a small constant times n.
Space: O(n). The array of characters is a copy of the input, and String(arr) builds a result of the same size. The swaps themselves use a single extra variable. If the string were already a mutable array of characters, the algorithm would need O(1) extra space.
Edge cases and common mistakes
- Empty string. The array is empty, so the first call is
reverse(&arr, 0, -1). The loop condition0 < -1is false, nothing happens, and the result is"". - One word.
"single"is reversed twice and comes back unchanged. - The last word. It isn't followed by a space, so
jstops atarr.count. The bounds check in the inner loop is what prevents a crash there. - Forgetting the second pass. Reversing only the whole string gives
eulb si yks. - Off-by-one in the word range. Reversing
itojinstead ofitoj - 1would drag the following space into the word. - Extra spaces. The lesson promises single spaces. With a doubled space, the code still runs and keeps the empty gap, so
"a b"gives"b a", but leading or trailing spaces stay where reversal puts them:" a b"becomes"b a ".
Testing
"sky is blue"gives"blue is sky"."single"gives"single".""gives""."a b"gives"b a".
