This problem statement is a part of LeetCode's learn card titled Arrays and Strings. Under the sub-heading conclusion.
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.
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: