Rearrange Words In A Sentence - Leetcode Solution

Problem:

Given a sentence text (A sentence is a string of space-separated words) in the following format:

First letter is in upper case. Each word in text are separated by a single space. Your task is to rearrange the words in text such that all words are rearranged in an increasing order of their lengths. If two words have the same length, arrange them in their original order.

Return the new text following the format shown above.

Example 1: Input: text = "Leetcode is cool" Output: "Is cool leetcode" Explanation: There are 3 words, "Leetcode" of length 8, "is" of length 2 and "cool" of length 4. Output is ordered by length and the new sentence is "Is cool leetcode".

Example 2: Input: text = "Keep calm and code on" Output: "On and keep calm code" Explanation: Output is ordered as follows: "On" 2 letters. "and" 3 letters. "keep" 4 letters in case of tie order by position in original text. "calm" 4 letters in case of tie order by position in original text. "code" 4 letters.

Solution:

We can solve this problem by the following steps:

First, we split the sentence into a list of words using the split() method.

Secondly, we create a dictionary with each word as the key and its length as the value.

Thirdly, we sort the dictionary by value.

Fourthly, we join the sorted words together into a sentence.

Finally, we return the sentence.

Here's the Python code to accomplish this:

class Solution: def arrangeWords(self, text: str) -> str:

    # split the sentence into a list of words
    words = text.split()
    
    # create a dictionary with each word as the key and its length as the value
    d = {}
    for word in words:
        d[word] = len(word)
    
    # sort the dictionary by value
    sorted_d = dict(sorted(d.items(), key=lambda x: x[1]))
    
    # join the sorted words together into a sentence
    sentence = ' '.join(sorted_d.keys())
    
    # capitalize the first letter of the sentence
    sentence = sentence.capitalize()
    
    # return the sentence
    return sentence

This solution has a time complexity of O(n log n), where n is the number of words in the sentence, due to the sorting operation.

1