Reverse Words in a String

LeetCode 151 | Difficulty: Medium

Medium

Problem Description

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 at least one space.

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

Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

Example 1:

Input: s = "the sky is blue"
Output: "blue is sky the"

Example 2:

Input: s = "  hello world  "
Output: "world hello"
Explanation: Your reversed string should not contain leading or trailing spaces.

Example 3:

Input: s = "a good   example"
Output: "example good a"
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.

Constraints:

- `1 Follow-up: If the string data type is mutable in your language, can you solve it in-place with O(1) extra space?

Topics: Two Pointers, String

---

Solutions

Solution 1: C# (Best: 88 ms)

Metric	Value
Runtime	88 ms
Memory	N/A
Date	2018-04-09

Solution

public class Solution {
    public string ReverseWords(string s) {
    char[] sArray = s.ToCharArray();
    int n = s.Length;
    StringBuilder sb = new StringBuilder();
    reverse(sArray, 0, n-1);
    int i = 0; int j = 0;
    
    while (i < n)
    {
        while (i < n && sArray[i] == ' ') i++;
        if(i==n) break;
        j = i;
        while (j < n && sArray[j] != ' ') j++;
        if (j == n && s[j-1] == ' ')
        {
            AddCharactersToStringBuilder(sArray, i, i, sb);
            break;
        }
        reverse(sArray, i, j - 1);
        if(sb.Length!=0) sb.Append(' ');
        AddCharactersToStringBuilder(sArray,i,j-1,sb);      
        i = j + 1;
    }
    return sb.ToString();


}

void AddCharactersToStringBuilder(char[] ar, int l, int r, StringBuilder sb)
{
    for (int i = l; i <= r; i++)
    {
        sb.Append(ar[i]);
    }
    
}

void reverse(char[] ar, int l, int r)
{
    while (l < r)
    {
        char temp = ar[l];
        ar[l] = ar[r];
        ar[r] = temp;
        l++;
        r--;
    }
}

}

---

Complexity Analysis

Approach	Time	Space
Two Pointers	$O(n)$	$O(1)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.