Algocademy Logo

Reverse Words in a String II - JavaScript Solution with O(n) Time Complexity


Given an input string s, reverse the order of the words.

A word is defined as a sequence of non-space characters. The words in s will be separated by one space for simplicity.

Return a string of the words in reverse order concatenated by a single space.

Example:

Input:  input = "sky is blue"

Output:  "blue is sky"

Understanding the Problem

The core challenge of this problem is to reverse the order of words in a given string. This is a common problem in text processing and has applications in various fields such as natural language processing and data formatting. A potential pitfall is to misunderstand the definition of a word or to mishandle the spaces between words.

Approach

To solve this problem, we can follow these steps:

  1. Split the input string into an array of words.
  2. Reverse the array of words.
  3. Join the reversed array back into a single string with spaces separating the words.

Let's discuss a naive solution and then an optimized solution:

Naive Solution

The naive solution involves splitting the string into words, reversing the array, and joining it back. This approach is straightforward but not the most efficient in terms of space complexity.

Optimized Solution

The optimized solution also involves splitting, reversing, and joining, but we can ensure it is done in a single pass to maintain O(n) time complexity.

Algorithm

Here is a step-by-step breakdown of the optimized algorithm:

  1. Split the input string by spaces to get an array of words.
  2. Reverse the array of words.
  3. Join the reversed array into a single string with spaces.

Code Implementation

// Function to reverse words in a string
function reverseWords(s) {
    // Step 1: Split the string into an array of words
    const words = s.split(' ');
    
    // Step 2: Reverse the array of words
    const reversedWords = words.reverse();
    
    // Step 3: Join the reversed array into a single string with spaces
    const reversedString = reversedWords.join(' ');
    
    // Return the reversed string
    return reversedString;
}

// Example usage
const input = "sky is blue";
const output = reverseWords(input);
console.log(output); // Output: "blue is sky"

Complexity Analysis

The time complexity of this solution is O(n), where n is the length of the input string. This is because splitting, reversing, and joining each take linear time. The space complexity is also O(n) due to the storage required for the array of words.

Edge Cases

Consider the following edge cases:

  • Empty string: The output should be an empty string.
  • String with one word: The output should be the same as the input.
  • String with multiple spaces between words: The output should handle multiple spaces correctly.

Examples:

reverseWords(""); // Output: ""
reverseWords("hello"); // Output: "hello"
reverseWords("  hello   world  "); // Output: "world hello"

Testing

To test the solution comprehensively, consider using a variety of test cases:

  • Simple cases with a few words.
  • Edge cases with empty strings and single words.
  • Complex cases with multiple spaces and special characters.

Example test cases:

console.log(reverseWords("sky is blue")); // Output: "blue is sky"
console.log(reverseWords("hello world")); // Output: "world hello"
console.log(reverseWords("a b c d e")); // Output: "e d c b a"
console.log(reverseWords("")); // Output: ""
console.log(reverseWords("singleword")); // Output: "singleword"

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

  • Break down the problem into smaller, manageable steps.
  • Think about edge cases and how to handle them.
  • Write clean, readable code with comments to explain your logic.
  • Practice similar problems to improve your problem-solving skills.

Conclusion

In this blog post, we discussed how to reverse the words in a string using JavaScript. We covered the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for improving your coding skills and preparing for technical interviews.

Additional Resources

For further reading and practice, consider the following resources: