Sorting the Sentence — LeetCode 1859 Python Solution

The problem

A sentence is a list of words that are separated by a single space with no leading or trailing spaces. Each word consists of lowercase and uppercase English letters.

Example

Input

s = "is2 sentence4 This1 a3"

Output

"This is a sentence"

Explanation

Sort the words in s to their original positions "This1 is2 a3 sentence4", then remove the numbers.

Python solution

class Solution:
    def sortSentence(self, s: str) -> str:
        ws = s.split()
        ans = [None] * len(ws)
        for w in ws:
            ans[int(w[-1]) - 1] = w[:-1]
        return " ".join(ans)

Complexity

Pattern: Sorting

Spend O(n log n) once to buy an ordering that makes the rest of the problem trivial. LeetCode 1859. Sorting the Sentence is filed here because LeetCode tags it Sorting, which is the vocabulary this hub collects.

The sorting guide has the Python template for the pattern and the 401 LeetCode problems that use it.

Related problems