Swift算法實(shí)現(xiàn)逐字翻轉(zhuǎn)字符串的方法示例

更新時(shí)間：2017年03月21日 11:11:36 作者：李峰峰博客

大家都知道翻轉(zhuǎn)字符串在字符串算法中算是比較常見(jiàn)的，下面這篇文章主要介紹了Swift算法實(shí)現(xiàn)逐字翻轉(zhuǎn)字符串的方法，文中給出了詳細(xì)的示例代碼，需要的朋友可以參考借鑒，下面來(lái)一起看看吧。

前言

翻轉(zhuǎn)字符串在字符串算法中算是比較常見(jiàn)的，而且被很多公司用作筆試題。”逐字翻轉(zhuǎn)字符串”是翻轉(zhuǎn)字符串的翻版，也是之前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?

簡(jiǎn)而言之就是：”the sky is blue”—>”blue is sky the”

所以，對(duì)于本文，要解決的算法是：

逐字翻轉(zhuǎn)字符串，例如："the sky is blue"—>"blue is sky the"

接下來(lái)看下實(shí)現(xiàn)思路和代碼。

實(shí)現(xiàn)思路及代碼

既然是字符串翻轉(zhuǎn)的翻版，我們就可以利用之前翻版字符串的思路去解決就可以了，不過(guò)這道題要有兩次翻轉(zhuǎn)：

第一次翻轉(zhuǎn)，整體翻轉(zhuǎn)：”the sky is blue” -> “eulb si yks eht”

第二次翻轉(zhuǎn)，單詞翻轉(zhuǎn)：”eulb si yks eht” -> “blue is sky the”

所以，首先可以實(shí)現(xiàn)一個(gè)可以翻轉(zhuǎn)局部和全部字符串的算法，傳入字符數(shù)組、startIndex 和 endIndex ，其中 startIndex 和 endIndex 分別為要翻轉(zhuǎn)的字符串的起始下標(biāo)和結(jié)束下標(biāo)，也就是要翻轉(zhuǎn) 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)
  
 }
 
}

之后就可以利用上面的算法去完成前面說(shuō)的兩次翻轉(zhuǎn)：

func reverseWords(_ str:String) -> String{
 
 var chars = [Character](str.characters)
 
 //首先翻轉(zhuǎn)整個(gè)字符串所有字符,"the sky is blue" -> "eulb si yks eht"
 _reverseStr(&chars,0,chars.count-1)
 
 //然后翻轉(zhuǎn)每個(gè)單詞中的字符，"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)
}

完整算法代碼：

//翻轉(zhuǎn)指定范圍的字符
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)
  
 }
 
}
 
//逐字翻轉(zhuǎn)字符串
func reverseWords(_ str:String) -> String{
 
 var chars = [Character](str.characters)
 
 //首先翻轉(zhuǎn)整個(gè)字符串所有字符,"the sky is blue" -> "eulb si yks eht"
 _reverseStr(&chars,0,chars.count-1)
 
 //然后翻轉(zhuǎn)每個(gè)單詞中的字符，"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"

總結(jié)

以上就是關(guān)于Swift算法實(shí)現(xiàn)逐字翻轉(zhuǎn)字符串的方法，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作能帶來(lái)一定的幫助，如果有疑問(wèn)大家可以留言交流，謝謝大家對(duì)腳本之家的支持。

您可能感興趣的文章: