[
string
two pointers
]
BinarySearch 0438 Sentence Reversal
Problem statement
https://binarysearch.com/problems/Sentence-Reversal/
Solution
Equal to Leetcode 0151. Reverse Words in a String.
Complexity
It is O(n)
for time and almost O(1)
for space: you need to reverse parts of string in place, instead of using [::-1]
.
Code
class Solution:
def solve(self, chars):
slow, n = 0, len(chars)
for fast in range(n):
if chars[fast] != " " or (fast > 0 and chars[fast] == " " and chars[fast-1] != " "):
chars[slow] = chars[fast]
slow += 1
if slow == 0: return ""
chars = chars[:slow-1] if chars[-1] == " " else chars[:slow]
chars.reverse()
slow, m = 0, len(chars)
for fast in range(m + 1):
if fast == m or chars[fast] == " ":
chars[slow:fast] = chars[slow:fast][::-1]
slow = fast + 1
return chars