DEV Community

Cover image for LeetCode Challenge: 151. Reverse Words in a String - JavaScript Solution πŸš€
Rahul Kumar Barnwal
Rahul Kumar Barnwal

Posted on

3 1 2 1 2

LeetCode Challenge: 151. Reverse Words in a String - JavaScript Solution πŸš€

Top Interview 150

Reversing the words in a string while handling multiple spaces efficiently is a common problem in string manipulation. Let's tackle LeetCode 151: Reverse Words in a String with an optimized solution and without using predefined methods like split or trim.


πŸš€ Problem Description

Given a string s, reverse the order of the words in the string:

  • A word is defined as a sequence of non-space characters.
  • Return the reversed string with a single space between the words.
  • Extra spaces before, after, or between words should be removed.

πŸ’‘ Examples

Example 1

Input: s = "the sky is blue"  
Output: "blue is sky the"
Enter fullscreen mode Exit fullscreen mode

Example 2

Input: s = "  hello world  "  
Output: "world hello"  
Explanation: Leading and trailing spaces are removed.
Enter fullscreen mode Exit fullscreen mode

Example 3

Input: s = "a good   example"  
Output: "example good a"  
Explanation: Multiple spaces are reduced to a single space.
Enter fullscreen mode Exit fullscreen mode

πŸ† Optimized JavaScript Solution

We will create a solution without relying on split or trim, aiming for O(n) time complexity and O(1) extra space.

Implementation

var reverseWords = function(s) {
    let n = s.length;
    let trimmed = "";
    let i = 0;

    while (i < n) {
        while (i < n && s[i] === ' ') i++;
        if (i >= n) break;

        let start = i;
        while (i < n && s[i] !== ' ') i++;
        if (trimmed.length > 0) trimmed = " " + trimmed;
        trimmed = s.slice(start, i) + trimmed;
    }

    return trimmed;
};
Enter fullscreen mode Exit fullscreen mode

πŸ” How It Works

  1. Remove Spaces and Extract Words:

    • Traverse the string while skipping spaces.
    • Identify words by their start and end indices.
    • Prepend each word to the result string.
  2. Handle Single Spaces Between Words:

    • Add a space before appending a word only if the result string is not empty.
  3. Return the Result:

    • By appending words in reverse order, we ensure that the words appear in reversed sequence.

πŸ”‘ Complexity Analysis

  • > Time Complexity: O(n), where n is the length of the string.
    • We traverse the string once while extracting words.
  • > Space Complexity: O(n), for the result string.

πŸ“‹ Dry Run

Input: " hello world "

Reverse Words in a String
Output: "world hello"


✨ Pro Tips for Optimization

  1. In-place Solution (Follow-Up):
    • Reverse the entire string.
    • Reverse each word in the reversed string.
    • Remove extra spaces.

Here’s the in-place implementation:

var reverseWords = function(s) {
    const reverse = (arr, start, end) => {
        while (start < end) {
            [arr[start], arr[end]] = [arr[end], arr[start]];
            start++;
            end--;
        }
    };

    let arr = Array.from(s);
    let n = arr.length;

    reverse(arr, 0, n - 1);

    let start = 0;
    for (let i = 0; i <= n; i++) {
        if (i === n || arr[i] === ' ') {
            reverse(arr, start, i - 1);
            start = i + 1;
        }
    }

    let result = [];
    for (let i = 0; i < n; i++) {
        if (arr[i] !== ' ' || (result.length > 0 && result[result.length - 1] !== ' ')) {
            result.push(arr[i]);
        }
    }

    if (result[result.length - 1] === ' ') result.pop();

    return result.join('');
};
Enter fullscreen mode Exit fullscreen mode

πŸ”‘ Complexity Analysis (In-Place Solution)

  • Time Complexity: O(n), due to three passes over the string.
  • Space Complexity: O(1), as no additional arrays or data structures are used.

πŸ“š Learn More

Check out the full explanation and code walkthrough on my Dev.to post:
πŸ‘‰ Reverse Words in a String - JavaScript Solution

What’s your approach to solving this problem? Let’s discuss below! πŸš€

JavaScript #LeetCode #CodingInterview #ProblemSolving

Top comments (3)

Collapse
 
rahulgithubweb profile image
Rahul Kumar Barnwal β€’

Follow Me on GitHub πŸš€

If you found this solution helpful, check out more of my projects and solutions on my GitHub profile.

Don't forget to follow for more updates!

Collapse
 
mariuam profile image
MARIUAM β€’

hiiii

Collapse
 
rahulgithubweb profile image
Rahul Kumar Barnwal β€’

hello

Image of Docusign

πŸ› οΈ Bring your solution into Docusign. Reach over 1.6M customers.

Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.

Learn more