PU Reverse Words in a String III

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.

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

Example:

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

Python Solution:

class Solution(object):
    def reverseWords(self, s):
        """
        :type s: str
        :rtype: str
        """
        return " ".join(word[::-1] for word in s.split(' '))

• Time complexity is O(N), or O(2N) which is same as O(N).
• Space complexity is O(N), because we return a new string.

C Solution:

void reverse(char *l, char *r) {
    r--;
    while (l < r) {
        char c = *l;
        *l = *r;
        *r = c;
        l++;
        r--;
    }
}

char* reverseWords(char* s) {
    char *l = s, *r = s;
    while (*r) {
        while (*r && *r != ' ') r++;
        reverse(l, r);
        if (!*r) return s;
        l = r = r + 1;
    }
    return s;
}

• Time complexity is O(N), or O(2N) which is same as O(N).
• Space complexity is O(1). We solve it in-place.

Summary:

• nothing to say.

LeetCode: 557. Reverse Words in a String III