给你一个字符串 text
，该字符串由若干被空格包围的单词组成。每个单词由一个或者多个小写英文字母组成，并且两个单词之间至少存在一个空格。题目测试用例保证 text
至少包含一个单词 。
请你重新排列空格，使每对相邻单词之间的空格数目都 相等 ，并尽可能 最大化 该数目。如果不能重新平均分配所有空格，请
将多余的空格放置在字符串末尾 ，这也意味着返回的字符串应当与原 text 字符串的长度相等。
返回 重新排列空格后的字符串 。
示例 1：
**输入：** text = " this is a sentence "
**输出：** "this is a sentence"
**解释：** 总共有 9 个空格和 4 个单词。可以将 9 个空格平均分配到相邻单词之间，相邻单词间空格数为：9 / (4-1) = 3 个。
示例 2：
**输入：** text = " practice makes perfect"
**输出：** "practice makes perfect "
**解释：** 总共有 7 个空格和 3 个单词。7 / (3-1) = 3 个空格加上 1 个多余的空格。多余的空格需要放在字符串的末尾。
示例 3：
**输入：** text = "hello world"
**输出：** "hello world"
示例 4：
**输入：** text = " walks udp package into bar a"
**输出：** "walks udp package into bar a "
示例 5：
**输入：** text = "a"
**输出：** "a"
提示：
1 <= text.length <= 100text 由小写英文字母和 ' ' 组成text 中至少包含一个单词
方法一：模拟
思路与算法
题目给定字符串 text，首先我们按照空格分割，得到单词集合，并统计空格数。
- 如果单词数为 1，则将全部的空格拼接到这个单词后面即可。
- 否则先计算出单词间的间隔，并按照单词及间隔来进行拼接，若拼接后仍有多余的空格，则将剩下的空格拼接在末尾即可。
代码
[sol1-Python3]1
2
3
4
5
6
7
8
| class Solution:
def reorderSpaces(self, text: str) -> str:
words = text.split()
space = text.count(' ')
if len(words) == 1:
return words[0] + ' ' * space
per_space, rest_space = divmod(space, len(words) - 1)
return (' ' * per_space).join(words) + ' ' * rest_space
|
[sol1-Java]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| class Solution {
public String reorderSpaces(String text) {
int length = text.length();
String[] words = text.trim().split("\\s+");
int cntSpace = length;
for (String word : words) {
cntSpace -= word.length();
}
StringBuilder sb = new StringBuilder();
if (words.length == 1) {
sb.append(words[0]);
for (int i = 0; i < cntSpace; i++) {
sb.append(' ');
}
return sb.toString();
}
int perSpace = cntSpace / (words.length - 1);
int restSpace = cntSpace % (words.length - 1);
for (int i = 0; i < words.length; i++) {
if (i > 0) {
for (int j = 0; j < perSpace; j++) {
sb.append(' ');
}
}
sb.append(words[i]);
}
for (int i = 0; i < restSpace; i++) {
sb.append(' ');
}
return sb.toString();
}
}
|
[sol1-C#]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| public class Solution {
public string ReorderSpaces(string text) {
int length = text.Length;
string[] words = text.Trim().Split(" ");
int cntSpace = length;
int wordCount = 0;
foreach (string word in words) {
if (word.Length > 0) {
cntSpace -= word.Length;
wordCount++;
}
}
StringBuilder sb = new StringBuilder();
if (words.Length == 1) {
sb.Append(words[0]);
for (int i = 0; i < cntSpace; i++) {
sb.Append(' ');
}
return sb.ToString();
}
int perSpace = cntSpace / (wordCount - 1);
int restSpace = cntSpace % (wordCount - 1);
for (int i = 0; i < words.Length; i++) {
if (words[i].Length == 0) {
continue;
}
if (sb.Length > 0) {
for (int j = 0; j < perSpace; j++) {
sb.Append(' ');
}
}
sb.Append(words[i]);
}
for (int i = 0; i < restSpace; i++) {
sb.Append(' ');
}
return sb.ToString();
}
}
|
[sol1-C++]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
| class Solution {
public:
vector<string_view> split(const string_view &str, char trim) {
int n = str.size();
vector<string_view> res;
int pos = 0;
while (pos < n) {
while(pos < n && str[pos] == trim) {
pos++;
}
if (pos < n) {
int curr = pos;
while(pos < n && str[pos] != trim) {
pos++;
}
res.emplace_back(str.substr(curr, pos - curr));
}
}
return res;
}
string reorderSpaces(string text) {
int length = text.size();
vector<string_view> words = split(text, ' ');
int cntSpace = length;
int wordCount = 0;
for (auto &word : words) {
if (word.size() > 0) {
cntSpace -= word.size();
wordCount++;
}
}
string ans;
if (words.size() == 1) {
ans.append(words[0]);
for (int i = 0; i < cntSpace; i++) {
ans.push_back(' ');
}
return ans;
}
int perSpace = cntSpace / (wordCount - 1);
int restSpace = cntSpace % (wordCount - 1);
for (int i = 0; i < words.size(); i++) {
if (words[i].size() == 0) {
continue;
}
if (ans.size() > 0) {
for (int j = 0; j < perSpace; j++) {
ans.push_back(' ');
}
}
ans.append(words[i]);
}
for (int i = 0; i < restSpace; i++) {
ans.push_back(' ');
}
return ans;
}
};
|
[sol1-C]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
| char** split(const char *str, char trim, int *returnSize) {
int n = strlen(str);
char **words = (char **)malloc(sizeof(char *) * n);
int wordsSize = 0, pos = 0;
while (pos < n) {
while(pos < n && str[pos] == trim) {
pos++;
}
if (pos < n) {
int curr = pos;
while(pos < n && str[pos] != trim) {
pos++;
}
words[wordsSize] = (char *)malloc(sizeof(char) * (pos - curr + 1));
strncpy(words[wordsSize], str + curr, pos - curr);
words[wordsSize++][pos - curr] = '\0';
}
}
*returnSize = wordsSize;
return words;
}
char * reorderSpaces(char * text){
int length = strlen(text);
int wordsSize = 0;
char **words = split(text, ' ', &wordsSize);
int cntSpace = length;
int wordCount = 0;
for (int i = 0; i < wordsSize; i++) {
int len = strlen(words[i]);
if (len > 0) {
cntSpace -= len;
wordCount++;
}
}
char *ans = (char *)malloc(sizeof(char) * (length + 1));
int pos = 0;
if (wordsSize == 1) {
pos += sprintf(ans + pos, "%s", words[0]);
for (int i = 0; i < cntSpace; i++) {
ans[pos++] = ' ';
}
ans[pos] = '\0';
free(words[0]);
free(words);
return ans;
}
int perSpace = cntSpace / (wordCount - 1);
int restSpace = cntSpace % (wordCount - 1);
for (int i = 0; i < wordsSize; i++) {
if (strlen(words[i]) == 0) {
continue;
}
if (pos > 0) {
for (int j = 0; j < perSpace; j++) {
ans[pos++] = ' ';
}
}
pos += sprintf(ans + pos, "%s", words[i]);
}
for (int i = 0; i < restSpace; i++) {
ans[pos++] = ' ';
}
ans[pos] = '\0';
for (int i = 0; i < wordsSize; i++) {
free(words[i]);
}
free(words);
return ans;
}
|
[sol1-JavaScript]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| var reorderSpaces = function(text) {
const length = text.length;
const words = [];
text.split(' ').forEach(e => {
if (e.length > 0) {
words.push(e);
}
});
let cntSpace = length;
for (const word of words) {
if (word.length) {
cntSpace -= word.length;
}
}
let sb = '';
if (words.length === 1) {
sb += words[0];
for (let i = 0; i < cntSpace; i++) {
sb += ' ';
}
return sb;
}
const perSpace = Math.floor(cntSpace / (words.length - 1));
const restSpace = cntSpace % (words.length - 1);
for (let i = 0; i < words.length; i++) {
if (i > 0) {
for (let j = 0; j < perSpace; j++) {
sb += ' ';
}
}
sb += words[i];
}
for (let i = 0; i < restSpace; i++) {
sb += ' ';
}
return sb;
};
|
[sol1-Golang]1
2
3
4
5
6
7
8
9
| func reorderSpaces(s string) (ans string) {
words := strings.Fields(s)
space := strings.Count(s, " ")
lw := len(words) - 1
if lw == 0 {
return words[0] + strings.Repeat(" ", space)
}
return strings.Join(words, strings.Repeat(" ", space/lw)) + strings.Repeat(" ", space%lw)
}
|
复杂度分析
- 时间复杂度：O(n)，其中 n 为字符串 text 的长度。
- 空间复杂度：O(n)，其中 n 为字符串 text 的长度，主要为返回的字符串空间开销。
