Day-16 Reverse words in a string III

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

1. Convert the entire string into a list. Split the string based on whitespaces.
2. Iterate over the list. Reverse each word. For reverse using slicing.
3. 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

1. We are already using a for loop to iterate over list. Time complexity - O(n).
2. We are reversing the string using slicing.
3. 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.

1. Split the string into words. Split using whitespaces.
2. Iterate over the list. Convert each word into letters.
3. Then do a reverse based on two-pointer approach. Once, the reverse is done to join those letters to form string again.
4. 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

1. We are using extra space. As we are creating a new list in the process.
2. There is a while loop inside of a for loop. This adds on to the time complexity.
3. That whole reverse logic was written to avoid using list.reverse().

Some follow up questions

1. What is the time complexity of reversing a string using slicing s[::-1]? (see solution 1)
2. As we are using slicing inside a for loop. Will the overall time-complexity of code be O(nk)? (refer to solution 1)
3. 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)?