前言
翻转字符串在字符串算法中算是比较常见的，而且被很多公司用作笔试题。”逐字翻转字符串”是翻转字符串的翻版，也是之前Google的面试题，原题是这样的：
|
1
2
3
4
5
6
7
|
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”—>”blue is sky the”
所以，对于本文，要解决的算法是：
逐字翻转字符串，例如："the sky is blue"—>"blue is sky the"
接下来看下实现思路和代码。
实现思路及代码
既然是字符串翻转的翻版，我们就可以利用之前翻版字符串的思路去解决就可以了，不过这道题要有两次翻转：
第一次翻转，整体翻转：”the sky is blue” -> “eulb si yks eht”
第二次翻转，单词翻转：”eulb si yks eht” -> “blue is sky the”
所以，首先可以实现一个可以翻转局部和全部字符串的算法，传入字符数组、startIndex 和 endIndex ，其中 startIndex 和 endIndex 分别为要翻转的字符串的起始下标和结束下标，也就是要翻转 startIndex 和 endIndex 之间（包含）的字符，代码如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
func _reverseStr( _ chars:inout [Character], _ startIndex:Int, _ endIndex:Int){ var startIndex = startIndex var endIndex = endIndex if startIndex <= endIndex { let tempChar = chars[endIndex] chars[endIndex] = chars[startIndex] chars[startIndex] = tempChar startIndex += 1 endIndex -= 1 _reverseStr(&chars,startIndex,endIndex) } } |
之后就可以利用上面的算法去完成前面说的两次翻转：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
func reverseWords(_ str:String) -> String{ var chars = [Character](str.characters) //首先翻转整个字符串所有字符,"the sky is blue" -> "eulb si yks eht" _reverseStr(&chars,0,chars.count-1) //然后翻转每个单词中的字符，"eulb si yks eht" -> "blue is sky the" var startIndex = 0 for endIndex in 0 ..< chars.count { if endIndex == chars.count - 1 || chars[endIndex + 1] == " " { _reverseStr(&chars, startIndex, endIndex) startIndex = endIndex + 2 } } return String(chars)} |
完整算法代码：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
//翻转指定范围的字符func _reverseStr( _ chars:inout [Character], _ startIndex:Int, _ endIndex:Int){ var startIndex = startIndex var endIndex = endIndex if startIndex <= endIndex { let tempChar = chars[endIndex] chars[endIndex] = chars[startIndex] chars[startIndex] = tempChar startIndex += 1 endIndex -= 1 _reverseStr(&chars,startIndex,endIndex) } } //逐字翻转字符串func reverseWords(_ str:String) -> String{ var chars = [Character](str.characters) //首先翻转整个字符串所有字符,"the sky is blue" -> "eulb si yks eht" _reverseStr(&chars,0,chars.count-1) //然后翻转每个单词中的字符，"eulb si yks eht" -> "blue is sky the" var startIndex = 0 for endIndex in 0 ..< chars.count { if endIndex == chars.count - 1 || chars[endIndex + 1] == " " { _reverseStr(&chars, startIndex, endIndex) startIndex = endIndex + 2 } } return String(chars)} reverseWords("the sky is blue") //return "blue is sky the" |
总结
以上就是关于Swift算法实现逐字翻转字符串的方法，希望本文的内容对大家的学习或者工作能带来一定的帮助，如果有疑问大家可以留言交流，谢谢大家对服务器之家的支持。
原文链接：http://www.imlifengfeng.com/blog/?p=643
