Reverse Words in a String III

Easy Arrays & Hashing Two Pointer Original on LeetCode

Reported atWiproInMobi

Reverse Words in a String III is a easy arrays & hashing problem solved with the two pointer pattern. The best approach, optimal (two pointers on a character array), runs in O(n) time and O(n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (split, reverse, join) up.

Problem

Given a sentence s, reverse the order of the characters inside every word while keeping the words themselves, and the single spaces between them, in their original order.

A word is a maximal run of non-space characters. Return the resulting string.

Examples

Example 1

Input
s = "code every morning"
Output
"edoc yreve gninrom"
Why
Each word is reversed on its own; the words stay in the same order.

Example 2

Input
s = "Go 2 it!"
Output
"oG 2 !ti"
Why
Digits and punctuation are ordinary characters of their word.

Example 3

Input
s = "a"
Output
"a"
Why
A single one-letter word is unchanged.

Constraints

  • 1 <= s.length <= 5 * 10^4
  • s contains printable ASCII characters.
  • There are no leading or trailing spaces, and words are separated by exactly one space.
  • There is at least one word.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (split, reverse, join)O(n)O(n)
Optimal (two pointers on a character array)O(n)O(n)

1Brute force (split, reverse, join)

TimeO(n)Every character is copied a constant number of times.
SpaceO(n)The word array, the reversed copies and the joined result.

Split the string on spaces, reverse every word into a new string, and join the reversed words back with single spaces.

  1. Split s on ' ' into words.
  2. For each word, build its reverse.
  3. Join the reversed words with ' '.
class Solution {
    public String reverseWords(String s) {
        String[] words = s.split(" ");
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < words.length; i++) {
            if (i > 0) sb.append(' ');
            sb.append(new StringBuilder(words[i]).reverse());
        }
        return sb.toString();
    }
}

2Optimal (two pointers on a character array)

TimeO(n)Each character is visited once by the scan and swapped at most once.
SpaceO(n)The char array (strings are immutable); no other buffers.

Copy the string into a character array once. Scan for each word's boundaries, and reverse the characters between them in place by swapping from both ends toward the middle. Spaces never move.

  1. Convert s to a char array c.
  2. Let start = 0. For i from 0 to n: when i == n or c[i] == ' ', reverse c[start..i-1] and set start = i + 1.
  3. Reverse: swap c[l] and c[r], then l++, r-- while l < r.
  4. Return the array as a string.
class Solution {
    public String reverseWords(String s) {
        char[] c = s.toCharArray();
        int n = c.length, start = 0;
        for (int i = 0; i <= n; i++) {
            if (i == n || c[i] == ' ') {
                int l = start, r = i - 1;
                while (l < r) {
                    char t = c[l];
                    c[l++] = c[r];
                    c[r--] = t;
                }
                start = i + 1;
            }
        }
        return new String(c);
    }
}

Edge cases to test

  • A single word
  • One-character words
  • Palindromic words that look unchanged

Hints

Hint 1

Find where each word starts and ends: it ends right before a space or at the end of the string.

Hint 2

Reverse each word in place with two pointers swapping from both ends.

FAQ

What is the best time complexity for Reverse Words in a String III?

Optimal (two pointers on a character array) runs in O(n) time and O(n) extra space. Each character is visited once by the scan and swapped at most once.

Which pattern does Reverse Words in a String III use?

It is a arrays & hashing problem that uses the two pointer pattern. Other problems with the same pattern: Two Sum II - Input Array Is Sorted, Valid Triangle Number, Container With Most Water.

Is there a brute force solution for Reverse Words in a String III?

Yes. Brute force (split, reverse, join) takes O(n) time and O(n) space. Split the string on spaces, reverse every word into a new string, and join the reversed words back with single spaces.

Which edge cases should I test for Reverse Words in a String III?

A single word; One-character words; Palindromic words that look unchanged.