Swift算法实现逐字翻转字符串的方法示例

大家都知道翻转字符串在字符串算法中算是比较常见的，下面这篇文章主要介绍了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?

简而言之就是：”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 之间（包含）的字符，代码如下：

									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)

									}

完整算法代码：

									//翻转指定范围的字符

									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"