Taro Logo

Reverse Words in a String II

Medium
Apple logo
Apple
2 views
Topics:
ArraysStringsTwo Pointers

Reverse Words in a String II

You are given a character array s representing a sentence, where words are separated by single spaces. Your task is to reverse the order of words in the sentence. You must perform this reversal in-place, meaning you cannot allocate extra space for a new array. You are only allowed to modify the original character array.

For example:

  1. Input: s = ['t', 'h', 'e', ' ', 's', 'k', 'y', ' ', 'i', 's', ' ', 'b', 'l', 'u', 'e'] Output: s = ['b', 'l', 'u', 'e', ' ', 'i', 's', ' ', 's', 'k', 'y', ' ', 't', 'h', 'e']

  2. Input: s = ['h', 'e', 'l', 'l', 'o'] Output: s = ['h', 'e', 'l', 'l', 'o']

  3. Input: s = ['a', ' ', 'b'] Output: s = ['b', ' ', 'a']

Constraints:

  • 1 <= s.length <= 10^5
  • s[i] is an English letter (uppercase or lowercase), digit, or space ' '.
  • There is at least one word in s.
  • All words in s are separated by a single space.

Write a function that takes the character array s as input and modifies it in-place to reverse the order of words.

Solution


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. Will the input string contain leading or trailing spaces, and should I trim them?
  2. Can the input string contain multiple spaces between words, and how should I handle them?
  3. Is the input guaranteed to contain at least one word, or could it be an empty string?
  4. Should the reversal be done in-place, modifying the original character array directly?
  5. Are there any special characters or non-alphanumeric characters that I should be aware of?

Brute Force Solution

Approach

The brute force method solves this by looking at every possible combination. Think of it like manually trying out different arrangements of the words in the string. We will reverse the entire string, then reverse each word individually.

Here's how the algorithm would work step-by-step:

  1. First, take the entire string and reverse it completely. So the last letter becomes the first, and so on.
  2. Next, go through the reversed string word by word.
  3. For each word you find, reverse that word individually. This puts the letters of each word back in the correct order, but keeps the words themselves in the reversed order.

Code Implementation

def reverse_words(list_of_characters):
    def reverse_substring(list_of_characters, start, end):
        while start < end:
            list_of_characters[start], list_of_characters[end] = list_of_characters[end], list_of_characters[start]
            start += 1
            end -= 1

    # Reverse the entire string to put words in reverse order
    reverse_substring(list_of_characters, 0, len(list_of_characters) - 1)

    start_index = 0
    for index in range(len(list_of_characters) + 1):
        if index == len(list_of_characters) or list_of_characters[index] == ' ':
            # Reverse each word to get letters in correct order
            reverse_substring(list_of_characters, start_index, index - 1)

            start_index = index + 1

Big(O) Analysis

Time Complexity
O(n)The algorithm first reverses the entire string of length n. This reversal takes O(n) time. Then, it iterates through the reversed string again, identifying each word and reversing it. Reversing each word also takes time proportional to the length of that word. Since all the word lengths added together equals the length of the string n, the total time spent reversing individual words is also O(n). Therefore, the overall time complexity is O(n) + O(n), which simplifies to O(n).
Space Complexity
O(1)The algorithm reverses the entire string in-place, meaning it modifies the input directly. The individual word reversals are also performed in-place using a constant number of variables to track start and end positions within the string. Therefore, no auxiliary data structures that scale with the input size N (the length of the string) are used. The algorithm's space usage remains constant, independent of the input string's length.

Optimal Solution

Approach

The trick to reversing words in place is to first reverse the entire string. After that, reverse each word individually. This approach avoids needing extra memory to store the reversed string or individual words.

Here's how the algorithm would work step-by-step:

  1. Reverse the entire string of characters. So, if the original string was 'the sky is blue', it becomes 'eulb si yks eht'.
  2. Now, go through the reversed string and reverse each word separately. In our example, 'eulb' becomes 'blue', 'si' becomes 'is', 'yks' becomes 'sky', and 'eht' becomes 'the'.
  3. The final result after reversing each word is 'blue is sky the', which is the desired output.

Code Implementation

def reverse_words(list_of_characters):
    def reverse_range(list_to_reverse, start_index, end_index):
        while start_index < end_index:
            list_to_reverse[start_index], list_to_reverse[end_index] = list_to_reverse[end_index], list_to_reverse[start_index]
            start_index += 1
            end_index -= 1

    # First, reverse the entire string.
    reverse_range(list_of_characters, 0, len(list_of_characters) - 1)

    start_of_word_index = 0
    for index in range(len(list_of_characters) + 1):
        # Identify word boundaries using spaces
        if index == len(list_of_characters) or list_of_characters[index] == ' ':
            # Reverse each word individually.
            reverse_range(list_of_characters, start_of_word_index, index - 1)

            # Move the start index to the next word.
            start_of_word_index = index + 1

Big(O) Analysis

Time Complexity
O(n)The algorithm first reverses the entire string, which takes O(n) time where n is the length of the string. Then, it iterates through the reversed string to reverse each word. Reversing each word also takes O(n) time in total because, in the worst case, every single character must be individually accessed and flipped during these smaller reversals. Since we perform two O(n) operations sequentially, the overall time complexity is O(n) + O(n) which simplifies to O(n).
Space Complexity
O(1)The algorithm operates in-place, meaning it modifies the original string directly. It primarily uses a constant number of variables for swapping characters during the reversal process and to keep track of word boundaries. Therefore, the auxiliary space required does not depend on the size of the input string N and remains constant.

Edge Cases

CaseHow to Handle
Null or empty input stringReturn immediately or throw an IllegalArgumentException as appropriate for the language.
String with only spacesTreat multiple spaces as single spaces, resulting in an empty or single-space string after reversal.
String with leading/trailing spacesTrim leading and trailing spaces before reversing the words to avoid extra spaces in the output.
Single word stringThe reversed string will be the same as the original string, so return the original.
String with consecutive multiple spaces between wordsReduce multiple spaces to single spaces during processing.
Maximum length string (memory constraints)Ensure the solution doesn't exceed memory limits and potentially consider in-place reversal if memory is a concern.
String containing non-ASCII charactersEnsure the string reversal algorithm handles Unicode characters correctly, using UTF-8 encoding or similar.
Integer overflow when calculating lengths or indicesUse appropriate data types (e.g., long) or validate input lengths to prevent integer overflow.