Solution to LeetCode 344 Reverse String & LeetCode 541 Reverse String II & LeetCode 151 Reverse Words in a String.
LeetCode 344
Reverse String (Easy) [link]
Time complexity O(n). Space complexity O(1).
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
left = 0
right = len(s)-1
while left<right:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1
LeetCode 541
Reverse String II (Easy) [link]
The idea is similar to LC 344. We reverse the first k elements for every 2k elements.
Time complexity O(n). Space complexity O(1).
class Solution:
def reverseStr(self, s: str, k: int) -> str:
def reverse(t):
left = 0
right = len(t)-1
while left<right:
t[left], t[right] = t[right], t[left]
left += 1
right -= 1
return t
res = list(s)
for i in range(0, len(res), 2*k):
res[i:i+k] = reverse(res[i:i+k])
return ''.join(res)
LeetCode 151
Reverse Words in a String (Medium) [link]
First reverse the whole string, then reverse each word. Time complexity O(n). Space complexity O(1).
class Solution:
def trim_space(self, s):
n = len(s)
left = 0
right = n-1
while s[left] == " ":
left += 1
while s[right] == ' ':
right -= 1
tmp = []
while left <= right:
if s[left] != ' ':
tmp.append(s[left])
elif tmp[-1] != ' ':
tmp.append(s[left])
left += 1
return tmp
def reverse(self, t, left, right):
while left < right:
t[left], t[right] = t[right], t[left]
left += 1
right -= 1
return None
def reverse_word(self, t):
start = 0
end = 0
n = len(t)
while start<n:
while end < n and t[end] != ' ':
end += 1
self.reverse(t, start, end-1)
start=end+1
end+=1
return None
def reverseWords(self, s: str) -> str:
l = self.trim_space(s)
self.reverse(l, 0, len(l)-1)
self.reverse_word(l)
return ''.join(l)
