Swift算法实战：翻转字符串

字符串在算法中经常遇到，下面以两道题目为例，学习如何进行字符串的翻转。

一、我们来一起看一道以前的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?

看到这道题的时候，先整理下思路，解题步骤分为两步如下：

1. 将整个字符串翻转，即遍历前后每个字符进行互换：
   the sky is blue --> eulb si yks eht
2. 逐个单词进行翻转， 遍历字符串根据“ ”空格字符获取单词，然后对每个单词进行翻转：
   eulb si yks eht --> blue is sky the

答题之前，我们先用 Tuple实现一个通用的字符串翻转的方法：

fileprivate func swap<T>(_ chars: inout [T], _ p: Int, _ q: Int) {
    (chars[p], chars[q]) = (chars[q], chars[p])
}

如果你正在使用swift 4.0，那实现起来更加简单

Swift 4.0 新增特性: String 又变成了集合类型
新增函数 reversed，实现字符串翻转。
下面是官方示例：

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 环境下，你会发现string.character这个方法在3.2的时候已经被遗弃，那结合上文提到的特性，重新实现了一下：

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的所有字符串，最后翻转整个字符串就实现了整个翻转。

按照下述3个步骤操作即可：

1. 首先将字符串分成两个部分，
   即X："the sky"，Y："is blue"
2. 先将X进行翻转：the sky-->yks eht，
   再讲Y进行翻转：is blue-->eulb si

3. 翻转上述步骤得到的结果字符串，即翻转字符串 "yks eht eulb si" 的两部分（yks eht和eulb si）给予反转，"yks eht eulb si" 得到 "is blue the sky"，这就实现了整个反转。
   如下图所示：

   
   reversed.png
   

   代码实现如下：

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 引用之前第一题的写好的函数
    _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)，达到了题目的要求。

参考资料：
https://www.jianshu.com/p/977736b08bd7
https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/01.01.md