1451. Rearrange Words in a Sentence
Problem Description
Given a sentence text
, which is a string comprised of space-separated words, you are tasked with rearranging the words according to their lengths. Notably, the sentence follows certain formatting rules: the first character of the sentence is uppercase, and each subsequent word is separated by a single space. Your job is to reorganize the sentence so that shorter words come first, maintaining the order of words of the same length. After rearranging, the modified sentence should also adhere to the initial format with the first letter capitalized and space-separated words.
Intuition
To solve this problem, the initial step is to break the sentence into individual words. This can be easily achieved by using the split
function in Python, which divides the string at each space and returns a list of words. Since the first word is capitalized, and the remaining words are not, we first need to convert the initial word to lowercase to ensure uniformity in formatting post-sorting.
Next, we sort the list of words based on their lengths. The sort
function in Python is stable, which means that if multiple elements have the same sorting keyāin this case, the length of the wordāthey will maintain their original order. This property is essential for meeting the requirement of preserving the order of words that have the same number of characters.
After sorting the words by length, we then need to capitalize the first word to match the sentence formatting rules. The title
method is used to capitalize the first character of the first word.
Finally, we join the sorted words back into a string, separating them with spaces, to construct the rearranged sentence. This sentence now has its words sorted by length while preserving the order of words of the same length and maintaining the initial formatting rule with the capitalized first letter.
Learn more about Sorting patterns.
Solution Approach
The solution approach can be broken down into the following steps, aligning with the instructions in the provided Python code:
-
Splitting the input sentence into words: This makes use of Python's string
split()
function, which breaks the string at each space character and returns a list of words. -
Converting the first word to lowercase: As the first letter of the input sentence is capitalized and we want to sort the words without being affected by their capitalization, the first word of the list is converted to lowercase using the
lower()
string method. -
Sorting the words by length: The sorted
words
list is achieved by calling thesort()
method with a key specifyinglen
, which indicates that the sorting criterion is the length of each word. As thesort()
method is stable, it retains the order of words that compare as equal (words of the same length). -
Capitalizing the first word of the sorted list: After sorting, to adhere to the problemās output format criteria, the first word of the sorted list should be capitalized. This is accomplished by replacing the first word with its titled version, using the
title()
string method, which capitalizes the first character of the string. -
Joining the sorted words into a sentence: The final sentence is constructed by combining the sorted words back together using the
join()
method with a" "
space as the separator.
The key algorithms and data structures used in this solution are:
- String manipulation methods:
split()
,lower()
,title()
, andjoin()
are used to divide and reformat the sentence accordingly. - The sorting algorithm used by Python's
sort()
method: It rearranges the elements of the list in place and is known for its efficiency and stability.
This solution elegantly leverages built-in Python functions to address the problem, ensuring that the approach is both readable and efficient.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's go through a small example to illustrate the solution approach described above. Imagine we have the sentence text
:
"The quick brown fox jumps over the lazy dog."
We aim to sort this sentence by the length of the words while preserving the formatting.
-
Splitting the input sentence into words:
We begin by splitting
text
into words usingsplit()
:words = text.split()
results in:["The", "quick", "brown", "fox", "jumps", "over", "the", "lazy", "dog"]
-
Converting the first word to lowercase:
We then convert the first word to lowercase:
words[0] = words[0].lower()
gives us:["the", "quick", "brown", "fox", "jumps", "over", "the", "lazy", "dog"]
-
Sorting the words by length:
Next, we sort the words by their lengths using the
sort()
method:words.sort(key=len)
sorts the list as:["the", "fox", "the", "dog", "over", "lazy", "quick", "brown", "jumps"]
Note that "the" appears before "fox" because it comes first in the original order.
-
Capitalizing the first word of the sorted list:
We capitalize the first word in the sorted list to conform to the initial sentence's formatting:
words[0] = words[0].title()
modifies the list to:["The", "fox", "the", "dog", "over", "lazy", "quick", "brown", "jumps"]
-
Joining the sorted words into a sentence:
Finally, we join the sorted words into a sentence:
sorted_text = ' '.join(words)
produces the rearranged sentence:"The fox the dog over lazy quick brown jumps."
The sentence now adheres to the initial format with the first word capitalized and the rest of the words sorted by length, respecting the order of words with equal length. The approach shows the effectiveness of Python's string manipulations and the stability of the sort function.
Solution Implementation
1class Solution:
2 def arrangeWords(self, text: str) -> str:
3 # Split the sentence into words
4 words = text.split()
5
6 # Convert the first word to lowercase to standardize sorting and capitalization
7 words[0] = words[0].lower()
8
9 # Sort the words based on their lengths
10 words.sort(key=len)
11
12 # Capitalize the first word of the arranged sentence
13 words[0] = words[0].capitalize()
14
15 # Join the words back into a sentence and return
16 return " ".join(words)
17
1class Solution {
2 public String arrangeWords(String text) {
3 // Split the input string into an array of words.
4 String[] words = text.split(" ");
5
6 // Convert the first word of the array to lowercase to standardize case for comparison.
7 words[0] = words[0].toLowerCase();
8
9 // Sort the array of words by the length of each word.
10 Arrays.sort(words, Comparator.comparingInt(String::length));
11
12 // Capitalize the first letter of the first word in the sorted array.
13 words[0] = words[0].substring(0, 1).toUpperCase() + words[0].substring(1);
14
15 // Join the words back into a single string with spaces and return the result.
16 return String.join(" ", words);
17 }
18}
19
1#include <vector>
2#include <sstream>
3#include <algorithm>
4#include <cctype>
5
6class Solution {
7public:
8 // Function to rearrange words such that they are sorted by length
9 string arrangeWords(string text) {
10 vector<string> words; // Vector to hold individual words
11 stringstream ss(text); // Stringstream to break text into words
12 string currentWord;
13
14 // Extract words from the stream and push them to the vector
15 while (ss >> currentWord) {
16 words.push_back(currentWord);
17 }
18
19 // Convert the first letter of the initial word to lowercase
20 words[0][0] = tolower(words[0][0]);
21
22 // Sort the words by their length using stable_sort to maintain
23 // the original order if lengths are equal
24 stable_sort(words.begin(), words.end(), [](const string& a, const string& b) {
25 return a.size() < b.size();
26 });
27
28 // Concatenate words back into a single string with spaces
29 string result;
30 for (const auto& word : words) {
31 result += word + " ";
32 }
33
34 // Remove the trailing space added from the last iteration
35 result.pop_back();
36
37 // Capitalize the first letter of the result
38 result[0] = toupper(result[0]);
39
40 // Return the final rearranged string
41 return result;
42 }
43};
44
1function arrangeWords(text: string): string {
2 // Split the input text into an array of words
3 let words: string[] = text.split(' ');
4
5 // Change the first word to lowercase to ensure uniformity before sorting
6 words[0] = words[0].toLowerCase();
7
8 // Sort the array of words based on their length in ascending order
9 words.sort((firstWord, secondWord) => firstWord.length - secondWord.length);
10
11 // Capitalize the first character of the first word in the sorted array
12 words[0] = words[0].charAt(0).toUpperCase() + words[0].slice(1);
13
14 // Join the words back into a string with spaces in between and return the result
15 return words.join(' ');
16}
17
Time and Space Complexity
The given Python code takes a string text
, splits it into words, and rearranges those words in ascending order of their lengths. The first word of the input text is converted to lowercase, and after sorting, the first word of the result is capitalized.
Time Complexity
The time complexity of the method mainly comes from three operations: splitting the text, sorting the words, and joining them back into a single string.
-
Splitting the text: This operation is
O(n)
wheren
is the length of the input string since it needs to go through the entire string once. -
Sorting the words: Python uses TimSort (a hybrid sorting algorithm derived from merge sort and insertion sort) for its sort() function, which has a worst-case time complexity of
O(m * log(m))
, wherem
is the number of elements in the list to sort. In this case,m
is the number of words. Note that since the sort key is the length of the words, and lengths can be computed in constant time, the complexity of the sorting step is purely based on the number of words. -
Joining the words: This is again
O(n)
as we need to combine all the words to form a single string, inserting a space in between each word.
Combining these, the overall time complexity of this function is O(n + m * log(m))
. In the worst case where m
is proportional to n
(i.e., n
is very close or equal to m
when the text has only space-separated single-character words), the time complexity simplifies to O(n * log(n))
.
Space Complexity
-
Additional List
words
: We store allm
words of the input text in a separate list, which gives usO(m)
space complexity. -
Internal workings of the sort function: Python's TimSort requires
O(m)
space in the worst case, however this is a stable sort, so it does not require extra space that is proportional ton
(the total number of characters).
Therefore, the space complexity is also O(m)
. If we again assume that m
is proportional to n
in the worst-case scenario, then the space complexity can be considered O(n)
.
Learn more about how to find time and space complexity quickly using problem constraints.
What data structure does Breadth-first search typically uses to store intermediate states?
Recommended Readings
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!