Reverse Words in a String III

• LeetCode: Reverse Words in a String IIIP
• Problem:

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.

• Note:

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"

• Analysis:

Use two pointers to find the start index and end index of a word.

Reverse every word and append white space.

• Code - Java:

class Solution {
    public String reverseWords(String s) {
        if (s == null || s.length() == 0) {
            return s;
        }
        int len = s.length();
        int left = 0;
        int right = 0;
        StringBuilder builder = new StringBuilder();
        while (true) {
            while (left < len && s.charAt(left) == ' ') {
                left++;
            }
            if (left == len) {
                break;
            }
            right = left;
            while (right < len && s.charAt(right) != ' ') {
                right++;
            }
            builder.append(new StringBuilder(s.substring(left, right)).reverse().toString());
            if (right < len) {
                builder.append(' ');
            }
            left = right;
        }
        return builder.toString();
    }
}

• Code - C++:

class Solution {
public:
    string reverseWords(string s) {
        int len = s.length();
        if (len == 0) {
            return s;
        }
        string builder;
        int left = 0;
        int right = 0;
        while (true) {
            while (left < len && s[left] == ' ') {
                left++;
            }
            if (left == len) {
                break;
            }
            right = left;
            while (right < len && s[right] != ' ') {
                right++;
            }
            string substr = s.substr(left, (right - left));
            reverse(substr.begin(), substr.end());
            builder += substr;
            if (right < len) {
                builder +=' ';
            }
            left = right;
        }
        return builder;
    }
};

• Code - Python:

class Solution(object):
    def reverseWords(self, s):
        """
        :type s: str
        :rtype: str
        """
        if s == None or len(s) == 0:
            return s
        sLen = len(s)
        builder = ""
        left, right = 0, 0
        while True:
            while left < sLen and s[left] == ' ':
                left += 1
            if left == sLen:
                break
            right = left
            while right < sLen and s[right] != ' ':
                right += 1
            builder += s[left:right][::-1]
            if right < sLen:
                builder += ' '
            left = right
        return builder

• Time Complexity: O(N), N is the length of the input string
• Space Compexity: O(N), N is the length of the input string