字符串在算法中經(jīng)常遇到，下面以兩道題目為例，學習如何進行字符串的翻轉疗隶。
一、我們來一起看一道以前的Google面試題翼闹。
Given an input string, reverse the string word by word.
A word is defined as a sequence of non-space characters.
The input string does not contain leading or trailing spaces and the words are always separated by a single space.
For example,
Given s = "the sky is blue",
return "blue is sky the".
Could you do it in-place without allocating extra space?
看到這道題的時候斑鼻，先整理下思路，解題步驟分為兩步如下：
- 將整個字符串翻轉猎荠，即遍歷前后每個字符進行互換：
the sky is blue --> eulb si yks eht - 逐個單詞進行翻轉坚弱， 遍歷字符串根據(jù)“ ”空格字符獲取單詞，然后對每個單詞進行翻轉：
eulb si yks eht --> blue is sky the
答題之前关摇，我們先用 Tuple實現(xiàn)一個通用的字符串翻轉的方法：
fileprivate func swap<T>(_ chars: inout [T], _ p: Int, _ q: Int) {
(chars[p], chars[q]) = (chars[q], chars[p])
}
如果你正在使用swift 4.0荒叶，那實現(xiàn)起來更加簡單
Swift 4.0 新增特性:
String又變成了集合類型
新增函數(shù)reversed，實現(xiàn)字符串翻轉输虱。
下面是官方示例：
let word = "Backwards"
for char in word.reversed() {
print(char, terminator: "")
}
// Prints "sdrawkcaB"
let reversedWord = String(word.reversed());
print("\n" + reversedWord)
// Prints "sdrawkcaB"
開始解題：
func reverseWords(s: String?) -> String? {
guard s != nil else {
return nil
}
var chars = Array(s!.characters), start = 0
_reverse(&chars, 0, chars.count - 1)
for i in 0 ..< chars.count {
if i == chars.count - 1 || chars[i + 1] == " " {
_reverse(&chars, start, i)
start = i + 2
}
}
return String(chars)
}
fileprivate func _reverse<T>(_ chars: inout [T], _ start: Int, _ end:Int){
var start = start, end = end
while start < end {
swap(&chars,start,end)
start += 1
end -= 1
}
}
時間復雜度還是O(n)些楣，整體思路和代碼簡單很多。
- 但在 Swift 4.0 環(huán)境下宪睹，你會發(fā)現(xiàn)
string.character這個方法在3.2的時候已經(jīng)被遺棄愁茁，那結合上文提到的特性，重新實現(xiàn)了一下：
func reverseWords(s: String?) -> String? {
guard s != nil else {
return nil
}
//翻轉整體字符串
let chars4 = String(s!.reversed())
print(chars4)
var startIdx = s?.startIndex, endIdex = s?.endIndex
var result = String()
//逐個單詞進行翻轉横堡，然后拼接
while let comma = chars4[startIdx!..<endIdex!].index(of: " ") {
result.append(String(chars4[startIdx!..<comma].reversed()) + " ")
startIdx = chars4.index(after: comma)
}
result.append(String(chars4[startIdx!..<endIdex!].reversed()))
print(result)
return String(result)
}
二埋市、如果將上面的題目 "the sky is blue" 改成返回結果是："is blue the sky" 那需要怎么做呢？
解題三步反轉法：
對于這個問題命贴，換一個角度思考一下道宅。
將一個字符串分成X和Y兩個部分，在每部分字符串上定義反轉操作胸蛛，先將X的所有字符串翻轉污茵，再翻轉Y的所有字符串，最后翻轉整個字符串就實現(xiàn)了整個翻轉葬项。
按照下述3個步驟操作即可：
- 首先將字符串分成兩個部分泞当，
即X："the sky"，Y："is blue" - 先將X進行翻轉：the sky-->yks eht民珍，
再講Y進行翻轉：is blue-->eulb si -
翻轉上述步驟得到的結果字符串襟士，即翻轉字符串 "yks eht eulb si" 的兩部分（yks eht和eulb si）給予反轉盗飒，"yks eht eulb si" 得到 "is blue the sky"，這就實現(xiàn)了整個反轉陋桂。
如下圖所示：
reversed.png
代碼實現(xiàn)如下：
func leftRotateString(str: String?, n: Int, m: Int) ->String? {
var m = m, n = n
m %= n //若要左移動大于n位逆趣，那么和%n 是等價的
var chars = Array(str!.characters)
print(String(chars))
//_reverse 引用之前第一題的寫好的函數(shù)
_reverse(&chars, 0, m - 1)//翻轉X，即：the sky-->yks eht
_reverse(&chars, m + 1, n - 1)//翻轉Y嗜历，即：is blue-->eulb si（注意處理空字符宣渗，m+1）
_reverse(&chars, 0, n - 1)//整體翻轉，即：yks eht eulb si-->is blue the sky
return String(chars)
}
這就是把字符串分為兩個部分梨州，先各自反轉再整體反轉的方法痕囱，時間復雜度為O(n)，空間復雜度為O(1)暴匠，達到了題目的要求鞍恢。
參考資料：
http://www.reibang.com/p/977736b08bd7
https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/01.01.md
