Background
This problem statement is a part of LeetCode's learn card titled Arrays and Strings. Under the sub-heading conclusion.
Problem Statement
Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.
Example 1
Input: "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"
Note: In the string, each word is separated by single space and there will not be any extra space in the string.
Solution Approach 1
- Convert the entire string into a list. Split the string based on whitespaces.
- Iterate over the list. Reverse each word. For reverse using slicing.
- Reconstruct the entire string. This time every word would be reversed.
class Solution:
def reverseWords(self, s: str) -> str:
s = s.split()
s1 = ''
for x in range(0, len(s)):
if x == len(s) - 1:
s1 += s[x][::-1]
else:
s1 += s[x][::-1] + ' '
return s1
Things to notice
- We are already using a for loop to iterate over list. Time complexity - O(n).
- We are reversing the string using slicing.
- Extra space is used here as well. As a new string is being constructed instead of making changes in-place.
Solution approach 2
This is probably the longer route to reach the solution.
- Split the string into words. Split using whitespaces.
- Iterate over the list. Convert each word into letters.
- Then do a reverse based on two-pointer approach. Once, the reverse is done to join those letters to form string again.
- Then again convert the list of reversed words to form the output string.
class Solution:
def reverseWords(self, s: str) -> str:
L = []
string = s.split()
for word in string:
y = list(word)
start = 0
end = len(y) - 1
while start < end:
temp = y[start]
y[start] = y[end]
y[end] = temp
start += 1
end -= 1
new_string = ''.join(y)
L.append(new_string)
return ' '.join(L)
Things to notice
- We are using extra space. As we are creating a new list in the process.
- There is a while loop inside of a for loop. This adds on to the time complexity.
- That whole reverse logic was written to avoid using list.reverse().
Some follow up questions
- What is the time complexity of reversing a string using slicing s[::-1]? (see solution 1)
- As we are using slicing inside a for loop. Will the overall time-complexity of code be O(nk)? (refer to solution 1)
- In solution approach 2. We are using a while loop inside of a for loop. This would lead to time complexity O(nk) or O(n^2)?
Top comments (1)
Thanks for continuing to post these, I love working through them when I have some time. Here's what I came up with for this one: