557. Reverse Words in a String III

EasyTwo PointersString
Leetcode Link

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:

  1. 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 (' ').

  2. Reverse each word individually. In Python, this is easily accomplished using slicing with [::-1]. This syntax creates a reversed copy of the sequence.

  3. 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

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:

  1. 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.

  2. 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.

  3. 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.

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

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

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:

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

    Input Sentence: "Hello World"

    After splitting: ["Hello", "World"]

  2. 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".

  3. 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
Not Sure What to Study? Take the 2-min Quiz：

What data structure does Breadth-first search typically uses to store intermediate states?

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.

  1. 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.

  2. 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:

  1. The s.split(' ') operation creates a list of words, which takes O(m) space, where m is the number of words.

  2. 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.

  3. 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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which type of traversal does breadth first search do?

Recommended Readings

Tech Interview Pattern | Two Pointers Introduction

Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers iframe width 560 height 315 src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe Two pointers is a common interview technique

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫