0557. Reverse Words in a String III

Easy | String | 28 ms (92.61%), 15.2 MB (10.81%)

❓ Problem Statement

Source: LeetCode - Reverse Words in a String III GitHub: Solution / Performance

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

✍🏻 Constraints & Example

Constraints:

• 1 <= s.length <= 5 * 10^4

• s contains printable ASCII characters.

• s does not contain any leading or trailing spaces.

• There is at least one word in s.

• All the words in s are separated by a single space.

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

Input: s = "God Ding"
Output: "doG gniD"

💡 Ideas

1. Extract words from the input string

2. Reverse the word then append to the returned string

🤖 Python3

class Solution:
    def reverseWords(self, s: str) -> str:
        
        # ==================================================
        #  String                                          =
        # ==================================================
        # time  : O(n), n is the length of s
        # space : O(n)
        
        l, r = 0, len(s) - 1
        word, ans = '', ''
        while l <= r:
            if s[l] == ' ':
                if word: ans += self.reverse(word) + ' '
                word = ''
                l += 1
                continue
                
            word += s[l]
            l += 1
        
        if word: ans += self.reverse(word) + ' '
            
        return ans[:-1]
            
    def reverse(self, s: str) -> str:
        s, l, r = [char for char in s], 0, len(s) - 1
        while l < r:
            s[l], s[r] = s[r], s[l]
            l += 1
            r -= 1
            
        ret = ''
        for char in s: ret += char
        return ret
    
    '''
    def reverseWords(self, s: str) -> str:
        return ' '.join(x[::-1] for x in s.split())
    '''

🤖 Java

class Solution {
    /**
     * @time  : O(n)
     * @space : O(n)
     */
    
    public String reverseWords(String input) {
        StringBuilder result = new StringBuilder();
        StringBuilder word = new StringBuilder();
        
        for (int i = 0; i < input.length(); i++) {
            if (input.charAt(i) != ' ') {
                word.append(input.charAt(i));
            } else {
                result.append(word.reverse());
                result.append(" ");
                word.setLength(0);
            }
        }
        
        result.append(word.reverse());
        return result.toString();
    }
}