How do you solve Reverse Words in a String on LeetCode?

Reverse Words in a String (LeetCode #151) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: Understanding how to manage spaces is crucial.

What is the brute force solution for Reverse Words in a String?

The brute force approach for Reverse Words in a String is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves splitting the string into words, reversing the list of words, and then joining them back together. This is straightforward but can be inefficient due to multiple passes over the string. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Reverse Words in a String?

Reverse Words in a String uses the following concepts: Two Pointers, String. The recommended patterns to study are: Two Pointers, String Manipulation.

What are the interview tips for Reverse Words in a String?

Always clarify the requirements about spaces before coding. Think about edge cases, like strings with only spaces. Practice writing clean and efficient code to improve readability.

What are common mistakes when solving Reverse Words in a String?

Not trimming the input string before processing. Failing to handle multiple spaces correctly.

#151

Reverse Words in a String

Medium

Two PointersStringTwo PointersString Manipulation

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal solution uses a two-pointer technique to reverse the words in place while managing spaces. This reduces the number of passes over the string and avoids extra space for storing words.

⚙️

Algorithm

4 steps

1Step 1: Trim the input string to remove leading and trailing spaces.
2Step 2: Use two pointers to find the start and end of each word, and reverse the characters in place.
3Step 3: Reverse the entire string to get the words in the correct order.
4Step 4: Clean up spaces by collapsing multiple spaces into a single space.

solution.py16 lines

1# Full working Python code
2def reverseWords(s):
3    s = s.strip()
4    words = list(s)
5    n = len(words)
6    start = 0
7    for end in range(n):
8        if words[end] == ' ':
9            if start != end:
10                words[start:end] = reversed(words[start:end])
11                start = end + 1
12    words[start:] = reversed(words[start:])
13    return ''.join(words).replace('  ', ' ')
14
15result = reverseWords('  hello world  ')
16print(result)

ℹ

Complexity note: The time complexity is O(n) because we only traverse the string a few times. The space complexity is O(1) since we are modifying the string in place without using extra space for another array.

1Understanding how to manage spaces is crucial.
2In-place modifications can save memory and improve efficiency.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.