LeetCode 151 - Reverse Words in a String

Programming Languages:

Difficulty: Medium

Problem Description

Requirement

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.

Examples

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

Solutions

Python Solution

Reversing words in a string can be accomplished using three steps:

  1. Split the string using a space as the separator and store in a list.
  2. Reverse the order of the list.
  3. Merge the list of strings separating each string with a space.
class Solution:
    def reverseWords(self, s: str) -> str:
        # Step 1: Split the string into a list of words
        words = s.split()
        
        # Step 2: Reverse the order of the list of words
        reversed_words = words[::-1]
        
        # Step 3: Return the joined reversed list of words separated by spaces
        return ' '.join(reversed_words)

SQL Server Solution

To reverse words in a string using SQL Server, the same steps will be performed:

  1. Split the string using a space as the separator and store in a list.
  2. Reverse the order of the list.
  3. Merge the list of strings separating each string with a space.

In SQL Server, to split a string that is separated by space, the `STRING_SPLIT` string function can be used:

The `STRING_SPLIT` string function is a table-valued function that splits a string into rows of substrings, based on a specified separator character.

Syntax

STRING_SPLIT ( string , separator [ , enable_ordinal ] )

Arguments

string

An expression of any character type (for example, nvarchar, varchar, nchar, or char).

separator

A single character expression of any character type (for example, nvarchar(1), varchar(1), nchar(1), or char(1)) that is used as separator for concatenated substrings.

enable_ordinal

An int or bit expression that serves as a flag to enable or disable the `ordinal` output column. A value of `1` enables the `ordinal` column. If `enable_ordinal` is omitted, NULL, or has a value of 0, the `ordinal` column is disabled.

Note: This option is only available to Azure SQL Database, Azure SQL Managed Instance, Azure Synapse Analytics (serverless SQL pool only), and SQL Server 2022 (16.x) and later versions.

Return Types

If the `ordinal` output column isn't enabled, `STRING_SPLIT` returns a single-column table whose rows are the substrings. The name of the column is `value`. It returns nvarchar if any of the input arguments are either nvarchar or nchar. Otherwise, it returns varchar. The length of the return type is the same as the length of the string argument.

If the `enable_ordinal` argument is passed a value of `1`, a second column named `ordinal` is returned that consists of the 1-based index values of each substring's position in the input string. The return type is bigint.

To use `STRING_SPLIT` to separate a string using a space as the separator, the Transact-SQL statement will look as follows:

DECLARE @s VARCHAR(100)

SET @s = 'the sky is blue';

SELECT value
FROM STRING_SPLIT(@s, ' ', 1);

| value |
|-------|
| the   |
| sky   |
| is    |
| blue  |

The second and third step, namely to reverse the order of the list and merge the reversed list of strings separating each word with a space, can be accomplished with the `STRING_AGG` string function.

The `STRING_AGG` string function concatenates the values of string expressions and places separator values between them, which is a space in this case. The separator isn't added at the end of string.

Syntax

STRING_AGG ( expression, separator ) [ <order_clause> ]

<order_clause> ::=   
    WITHIN GROUP ( ORDER BY <order_by_expression_list> [ ASC | DESC ] )

Arguments

expression

Is an expression of any type. Expressions are converted to `NVARCHAR` or `VARCHAR` types during concatenation. Non-string types are converted to `NVARCHAR` type.

separator

Is an expression of `NVARCHAR` or `VARCHAR` type that is used as separator for concatenated strings. It can be literal or variable.

<order_clause>

Optionally specify order of concatenated results using `WITHIN GROUP` clause:

WITHIN GROUP ( ORDER BY <order_by_expression_list> [ ASC | DESC ] )

<order_by_expression_list>

A list of non-constant expressions that can be used for sorting results. Only one order_by_expression is allowed per query. The default sort order is ascending.

Using the `STRING_AGG` string function to merge a list of strings in sorted in reverse order separating each word with a space, and adding it to the query earlier that uses the `STRING_SPLIT` to split a string of words separated by space, here's how the final query will look like that will reverse words in a string:

DECLARE @s VARCHAR(100)

SET @s = 'the sky is blue';

SELECT STRING_AGG(value, ' ') WITHIN GROUP (ORDER BY ordinal DESC) AS [Output]
FROM STRING_SPLIT(@s, ' ', 1)
WHERE value != '';

| Output          |
|-----------------|
| blue is sky the |

Related Articles: