title: Algorithm_ReverseWords
tags:
- Technology
- Algorithm
date: 2022-04-15 09:24#
Algorithm_ReverseWords#
Reverse Words in a String III#
Given a string s, reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.
Example 1:
Input: s = "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"
Example 2:
Input: s = "God Ding"
Output: "doG gniD"
Solution 1#
Logic:
Split the string into an array based on whitespace, then iterate through the array and use the reversed method on each string. Finally, join the array back into a string using whitespace.
Code:
class Solution {
func reverseWords(_ s: String) -> String {
let list = s.components(separatedBy: " ")
var results: [String] = []
for str in list {
let reverseStr = String(str.reversed())
results.append(reverseStr)
}
return results.joined(separator: " ")
}
}
Although this solution works, it does not utilize the Two Pointers algorithm. Another solution is to use Two Pointers. First, convert the string into a character array, then iterate through the array. If the current character is a whitespace, swap the elements between the previous whitespace and the current whitespace.
Code:
class Solution {
func reverseWords(_ s: String) -> String {
var characters = Array(s)
var start = 0
var end = 0
for i in 0..<characters.count {
let c = characters[i]
if String(c) == " " {
// Reverse the elements between the previous whitespace and the current whitespace
end = i - 1
swapList(&characters, start, end)
start = i + 1
}
}
swapList(&characters, start, characters.count-1)
return String(characters)
}
func swapList(_ characters: inout [Character], _ start: Int, _ end: Int) {
var mutStart = start
var mutEnd = end
while mutStart < mutEnd {
characters.swapAt(mutStart, mutEnd)
mutStart += 1
mutEnd -= 1
}
}
}