algoadvance

Leetcode 557. Reverse Words in a String III

Problem Statement

Given a string s, 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: s = "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"

Example 2:

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

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.

Clarifying Questions

1. Q: Are we guaranteed that the input string will not contain multiple consecutive spaces?
   • A: Yes.
2. Q: Is the input string s mutable, or should we consider creating a new result string?
   • A: Strings in Java are immutable, so we should consider preparing a new result string or using a mutable data structure like StringBuilder.

Strategy

1. Break Down the Problem:
   • First, split the input string s by spaces to get individual words.
   • Reverse each word.
   • Join the reversed words by a space to form the final result.
2. Steps:
   • Split the string using s.split(" ").
   • Reverse each word.
   • Use String.join(" ", <list of reversed words>) to combine the reversed words back into a single string.

Code

public class Solution {
    public String reverseWords(String s) {
        // Split the input string into words
        String[] words = s.split(" ");
        
        // Reverse each word
        for (int i = 0; i < words.length; i++) {
            words[i] = new StringBuilder(words[i]).reverse().toString();
        }
        
        // Join the reversed words with space
        return String.join(" ", words);
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        // Test cases
        System.out.println(solution.reverseWords("Let's take LeetCode contest")); // "s'teL ekat edoCteeL tsetnoc"
        System.out.println(solution.reverseWords("God Ding")); // "doG gniD"
    }
}

Time Complexity

The time complexity of this solution is O(n), where n is the length of the input string s. This is because:

• Splitting the string into words is O(n).
• Reversing each word is O(n) in total (each character is reversed exactly once).
• Joining the words back into a string is O(n).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?