LeetCode: Reverse Words in a String III

Description

Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.

Example 1:

Input: "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"

Note: In the string, each word is separated by single space and there will not be any extra space in the string.

Straightforward Solution

For an simple challenge, I trend to write the a simple but straightforward solution firstly. Iterate all the words in input string, and reverse each word.

class Solution {
public:
    string reverse(string s) {
        int l = 0;
        int r = s.size() - 1;
        while(l <= r)
            swap(s[l++], s[r--]);
        return s;
    }
    string reverseWords(string s) {
        string ans = "";
        string word = "";
        int l = 0;
        int r = 0;
        while(l < s.size()) {
            r = l;
            word = "";
            
            //try to find the end of a word
            while(r < s.size() && s[r] != ' ')
                word += s[r++];

            //reverse the word, and append it to answer
            if(word.size() > 0) {
                ans += (ans.size() > 0 ? " " : "") + reverse(word);
            }
            while(s[r] == ' ') r++;
            l = r;
        }
        return ans;
    }
};

An optimization: In-place policy

For the programming languages such as C/C++, Ruby, PHP, Swift, which we can modify the input string. We can use the In-place policy to reduce the extra copy instructions.

class Solution {
public: 
    string reverseWords(string s) {
        int length = s.length();
        int i = 0;
        while (i < length) {
            int start = i;
            while (i < length && s[i] != ' ') {
                i++;
            }

            //reverse the word in-place!
            int left = start, right = i - 1;
            while (left < right) {
                swap(s[left], s[right]);
                left++;
                right--;
            }

            //continue to skip whitespace
            while (i < length && s[i] == ' ') {
                i++;
            }
        }
        return s;
    }
};

Python

Because strings are immutable in Python, it is not feasible to traverse the string to exchange character positions within each word, but with the slices in Python, we can get a more elegant implementation.

For example:

>>> line = "I love Python"
>>> line.split(" ")
['I', 'love', 'Python']
>>> line.split(" ")[::-1]
['Python', 'love', 'I']
>>> " ".join(line.split(" ")[::-1])
'Python love I'
>>> " ".join(line.split(" ")[::-1])[::-1]
'I evol nohtyP'

So the solution for Python is:

class Solution(object):
    def reverseWords(self, s):
        return " ".join(s.split(" ")[::-1])[::-1]

Preparing for an interview? Check out this!

Join my Email List for more insights, It's Free!😋

← LeetCode: Relative Sort Array LeetCode: Sort Array by Increasi... →