557. Reverse Words in a String III

Problem Description

The problem presents a task where we are given a string s that represents a sentence. The goal is to reverse the sequence of characters in each individual word contained within the sentence, while maintaining the original order of the words and preserving the spaces between them. We are not required to reverse the entire sentence, but only individual words within it.

Intuition

The intuition behind the solution is straightforward. We break down the problem into smaller, logical steps. These steps are:

Split the given string s into individual words. A word is defined as a sequence of characters separated by spaces. We use the split() method in Python, which splits a string by the specified delimiter, in this case, a space (' ').
Reverse each word individually. In Python, this is easily accomplished using slicing with [::-1]. This syntax creates a reversed copy of the sequence.
Join the reversed words back together with a space (' ') as a separator to form a new string that represents the sentence with each word's characters in reverse order. We do this using the join() method, which combines all the elements of an iterable (like a list of words) into a single string, separated by the specified string (a space in our case).

The provided solution encapsulates this intuition into a one-liner by combining all the steps using a list comprehension and the join() method.

Learn more about Two Pointers patterns.

Solution Approach

The implementation of the solution utilizes a combination of string methods and list comprehensions, which are powerful features of Python's standard library. The step-by-step approach is as follows:

Splitting the String: The first step in the algorithm is to take the input string s which represents the sentence and split it into a list of words. This is accomplished with s.split(' '). The split method takes a delimiter, which in this case is a space (' '), and returns a list of substrings.
Reversing Each Word: Next, we need to reverse each word within the list. Python's slicing syntax can reverse a sequence when used with the step parameter set to -1 ([::-1]). We use a list comprehension to apply this reversal to each word in the list, resulting in [t[::-1] for t in s.split(' ')]. This piece of code iterates over each word t in the list of words created from the original sentence and creates a new list with each word reversed.
Joining the Words: Finally, we need to reassemble the sentence with each word's characters reversed but maintaining the original word order. The join() method is used to concatenate the elements of the list into a single string. ' '.join(...) takes each element of the iterable provided (the list of reversed words) and joins them into a single string separated by spaces. This restores the structure of the original sentence with spaces intact except that each word is now reversed.

The combination of split(), slicing, list comprehension, and join() methods provide a concise and efficient solution to the problem. Data structures like lists assist with managing collections of words, and the built-in string operations in Python handle the manipulation required without the need for more complex algorithms or patterns.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's take a simple sentence: "Hello World". Our task is to reverse the characters in each word. Following the solution approach, we'd perform the following steps:

Splitting the String: We start by splitting the string into individual words using s.split(' ').

Input Sentence: "Hello World"

After splitting: ["Hello", "World"]
Reversing Each Word: Using Python's slicing feature, we reverse each word in the list.

Reversed words: ["olleH", "dlroW"]

Mechanism: For string "Hello", "Hello"[::-1] becomes "olleH"; for "World", "World"[::-1] becomes "dlroW".
Joining the Words: With all words reversed, we join them back together with spaces between them to form a coherent sentence.

Final Output: "olleH dlroW"

Method used: ' '.join(["olleH", "dlroW"])

The complete Python expression for this would be ' '.join([word[::-1] for word in "Hello World".split(' ')]), which would evaluate to the expected output: "olleH dlroW".

Solution Implementation

1class Solution:
2    def reverseWords(self, s: str) -> str:
3        # Split the input string into words using a space as the delimiter.
4        words = s.split(' ')
5      
6        # Reverse each word in the list of words.
7        reversed_words = [word[::-1] for word in words]
8
9        # Join the reversed words back into a string with spaces between them.
10        reversed_sentence = ' '.join(reversed_words)
11      
12        # Return the reversed sentence.
13        return reversed_sentence
14

1class Solution {
2    public String reverseWords(String s) {
3        // StringBuilder to accumulate the final result
4        StringBuilder result = new StringBuilder();
5      
6        // Splitting the input string s into words separated by spaces
7        String[] words = s.split(" ");
8      
9        // Iterating through each word in the array
10        for (String word : words) {
11            // For each word, reverse it by iterating from the end to the start
12            for (int i = word.length() - 1; i >= 0; --i) {
13                // Append each character to result
14                result.append(word.charAt(i));
15            }
16            // After reversing, add a space to separate the words
17            result.append(" ");
18        }
19      
20        // Return the string representation of result
21        // We exclude the last space using substring to match the required output
22        return result.substring(0, result.length() - 1);
23    }
24}
25

1#include <algorithm> // Include algorithm library for std::reverse
2#include <string>    // Include string library for std::string
3
4class Solution {
5public:
6    // Function to reverse each word in a string.
7    string reverseWords(string s) {
8        // Iterate over the entire string.
9        for (int start = 0, len = s.size(); start < len; ++start) {
10            if (s[start] == ' ') continue; // Skip spaces.
11
12            // Find the end of the current word.
13            int end = start;
14            while (end < len && s[end] != ' ')
15                ++end;
16
17            // Reverse the current word.
18            std::reverse(s.begin() + start, s.begin() + end);
19
20            // Move the start to the end of the current word.
21            start = end;
22        }
23
24        return s; // Return the modified string.
25    }
26};
27

1// Function to reverse each word in a given string s.
2function reverseWords(s: string): string {
3    // Split the string by one or more whitespace characters.
4    return s
5        .split(/\s+/)
6        // Map each word in the array to its reversed form.
7        .map((word: string) => {
8            // Initialize an empty string to store the reversed word.
9            let reversedWord = '';
10            // Iterate over each character in the word.
11            for (const char of word) {
12                // Prepend the character to the reversedWord to reverse the word.
13                reversedWord = char + reversedWord;
14            }
15            // Return the reversed word.
16            return reversedWord;
17        })
18        // Join the reversed words back into a single string with spaces.
19        .join(' ');
20}
21

Time and Space Complexity

Time Complexity

The time complexity of the code mainly consists of two parts: splitting the string into words and reversing individual words.

Splitting the string into words using s.split(' ') has a time complexity of O(n) where n is the length of the string s. This is because we have to go through the entire string to find the spaces to split it into words.
Reversing each word and joining them happens in the list comprehension. Reversing a word of length k takes O(k) time, and we do this for each word. Assuming m words result from the split, and the average length of a word is k, the total time for this operation is O(m*k).

Assuming k is roughly equal to n/m (i.e., the average length of a word is proportional to the total length of the string divided by the number of words), the overall time complexity would be O(n + m*(n/m)) which simplifies to O(n + n) and finally to O(n).

Space Complexity

The space complexity of the code can be broken down as follows:

The s.split(' ') operation creates a list of words, which takes O(m) space, where m is the number of words.
The list comprehension [t[::-1] for t in s.split(' ')] generates a new list that contains the reversed words. This list also takes O(m) space.
When these words are joined to form the final string, this string would have the same length as the input string, O(n) space.

Hence, if we consider the space required for the input s, output string, and the intermediate list of words, the space complexity is O(n + m + m). Since we know that 2m is less than n (as m is the number of words, and there must be at least one character per word), we can approximate the space complexity to be O(n).

The final space complexity is thus O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

It's faster

It has better space complexity

Order of computer subproblems does not matter

It has better time complexity

I don't know