You are given a string text of words that are placed among some number of spaces. Each word consists of one or more lowercase English letters and are separated by at least one space. It's guaranteed that text contains at least one word.
Rearrange the spaces so that there is an equal number of spaces between every pair of adjacent words and that number is maximized. If you cannot redistribute all the spaces equally, place the extra spaces at the end, meaning the returned string should be the same length as text.
Return the string after rearranging the spaces.
Example 1:
Input: text = " this is a sentence " Output: "this is a sentence" Explanation: There are a total of 9 spaces and 4 words. We can evenly divide the 9 spaces between the words: 9 / (4-1) = 3 spaces.
Example 2:
Input: text = " practice makes perfect" Output: "practice makes perfect " Explanation: There are a total of 7 spaces and 3 words. 7 / (3-1) = 3 spaces plus 1 extra space. We place this extra space at the end of the string.
Constraints:
1 <= text.length <= 100text consists of lowercase English letters and ' '.text contains at least one word.
The description was taken from https://leetcode.com/problems/rearrange-spaces-between-words/.
#O(N) Time, O(N) Space
class Solution:
def reorderSpaces(self, text: str) -> str:
words = []
spaces = 0 for char in text:
if char == " ":
spaces += 1
data = text.split(" ")
for word in data:
if word != "":
words.append(word)
word_count = len(words)
if word_count < 2:
return words[0] + spaces * " "
quotient = spaces // (word_count - 1)
remainder = spaces % (word_count - 1)
for word in words:
output.append(word)
return (" " * quotient).join(words) + " " * remainderThis question comes down to counting the words of the input string, counting the spaces, then making use of the division and modulo operators to find how many spaces divide evenly, but also how many remainders there will be.
One tricky thing to consider is we will be dividing the spaces evenly by the word count minus one since we are trying to fit spaces between words.
Other than that, this solution will be how we'd expect.
We'll go through the input string and count the spaces, count the words, then calculate the quotient and remainder. We will then pad the words with the quotient spaces and fit whatever remainder spaces we have at the end before returning the string.
Let's start by initializing our words list and also our spaces count.
words = []
spaces = 0
Next, we will go through the text and count each space.
for char in text:
if char == " ":
spaces += 1
After, we'll clean the data by splitting the string between the spaces.
data = text.split(" ")
For each word in the data, if the word isn't a blank string then we will add it to our words list.
for word in data:
if word != "":
words.append(word)
From there, we will get our word count.
word_count = len(words)
We'll need to handle an edge case here where the input only has one word.
If we have a word and spaces, then we will have no two words to fit the spaces between. If this is the case, then we will just return the word with all of the spaces coming after it.
Also, if we only have one word and we tried to subtract one from it then divide by it here in a moment, then we will get an error for trying to divide by zero.
if word_count < 2:
return words[0] + spaces * " "
Now we will get the count of spaces we can fit in between the words, and also the remainder.
quotient = spaces // (word_count - 1)
remainder = spaces % (word_count - 1)
Finally, all we need to do now is join back together the words padded by the quotient spaces, then add on the remainder spaces at the end.
return (" " * quotient).join(words) + " " * remainder