EasyNo. 1859
Sorting the Sentence — LeetCode 1859 Python Solution
- Pattern
- Sorting
- Topics
- String, Sorting
- Reading time
- 2 min
- Source
- leetcode.com
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
- Time
- O(n)
- Space · auxiliary
- O(n)where n is the length of the string s
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
| No. | Problem | Difficulty |
|---|---|---|
| 0539 | Minimum Time Difference | Medium |
| 0899 | Orderly Queue | Hard |
| 0937 | Reorder Data in Log Files | Medium |
| 1451 | Rearrange Words in a Sentence | Medium |
| 2785 | Sort Vowels in a String | Medium |
| 0056 | Merge Intervals | Medium |
Frequently asked questions
- How hard is LeetCode 1859. Sorting the Sentence?
LeetCode 1859. Sorting the Sentence is rated Easy on LeetCode.
- What is the time complexity of LeetCode 1859. Sorting the Sentence?
The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 1859. Sorting the Sentence?
The Python solution on this page uses O(n), where n is the length of the string s auxiliary space.
- What topics does LeetCode 1859. Sorting the Sentence cover?
LeetCode 1859. Sorting the Sentence is tagged String and Sorting on LeetCode.