Problem Statement
Given an input string, reverse the string word by word.
For example:
Given s = “
the sky is blue”,
return “
blue is sky the”.
Clarification:
- What constitutes a word?
A sequence of non-space characters constitutes a word. - Could the input string contain leading or trailing spaces?
Yes. However, your reversed string should not contain leading or trailing spaces. - How about multiple spaces between two words?
Reduce them to a single space in the reversed string.
Original LeetCode problem page
My Solution in Swift
My first version uses a bunch of Swift built-in functions
|
1 2 3 4 5 |
func reverseWords(s: String) -> String { var tmp = s.componentsSeparatedByCharactersInSet(NSCharacterSet.whitespaceCharacterSet()) tmp = tmp.filter{ $0 != "" }.reverse() return " ".join(tmp) } |
My second version does all the works myself
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
func reverseWords(s: String) -> String { var newS: String = "" var bufferS: String = "" func joinBufferS() { if !bufferS.isEmpty { let midS = newS.isEmpty ? "" : " " newS = bufferS + midS + newS bufferS = "" } } for c in s { if String(c) == " " { joinBufferS() } else { bufferS += String(c) } } joinBufferS() return newS } |
The first version runs faster (284 ms vs 386 ms). The second version is slowed down by character comparison on line 12. There, I convert the character to be compared from Character to String type first. If I did the comparison directly using Character type, i.e. c == " " , it is even slower (608 ms vs 386 ms). I guess the slow character comparison in Swift is due to its unicode support and the fact that each Character instance is an extended grapheme cluster instead of a simple ASCII integer. Hope Apple can improve the speed of this in the future.
Try It Yourself
1: each links to a blog post of mine that is dedicated to the problem
2: total execution time of a solution on my MacBook Pro (Late 2013, 2.6 GHz Intel Core i7, 16 GB 1600 MHz DDR3). Each solution is compiled with following command:
$ swiftc -O -sdk `xcrun --show-sdk-path --sdk macosx` json.swift main.swift -o mySolution
The total execution time is the average of 10 runs.
3: these test cases are semi-automatically :P retrieved from LeetCode Online Judge system and are kept in JSON format
4: each Xcode project includes everything (my Swift solution to a problem, its JSON test cases and a driver code to test the solution on those test cases)
| Problem1 | Time2 | Test Cases3 | My Xcode Project4 |
| Reverse Words in a String | 268.937ms |