题目描述
给你一个字符串 message 和一个正整数 limit 。
你需要根据 limit 将 message 分割 成一个或多个 部分 。每个部分的结尾都是 "<a/b>" ，其中 "b" 用分割出来的总数 替换， "a" 用当前部分所在的编号 替换 ，编号从 1 到 b 依次编号。除此以外，除了最后一部分长度 小于等于 limit 以外，其他每一部分（包括结尾部分）的长度都应该 等于 limit 。
你需要确保分割后的结果数组，删掉每部分的结尾并 按顺序 连起来后，能够得到 message 。同时，结果数组越短越好。
请你返回 message 分割后得到的结果数组。如果无法按要求分割 message ，返回一个空数组。
示例 1：
输入：message = "this is really a very awesome message", limit = 9
输出：["thi<1/14>","s i<2/14>","s r<3/14>","eal<4/14>","ly <5/14>","a v<6/14>","ery<7/14>"," aw<8/14>","eso<9/14>","me<10/14>"," m<11/14>","es<12/14>","sa<13/14>","ge<14/14>"]
解释：
前面 9 个部分分别从 message 中得到 3 个字符。
接下来的 5 个部分分别从 message 中得到 2 个字符。
这个例子中，包含最后一个部分在内，每个部分的长度都为 9 。
可以证明没有办法分割成少于 14 个部分。
示例 2：
输入：message = "short message", limit = 15
输出：["short mess<1/2>","age<2/2>"]
解释：
在给定限制下，字符串可以分成两个部分：
- 第一个部分包含 10 个字符，长度为 15 。
- 第二个部分包含 3 个字符，长度为 8 。
提示：
1 <= message.length <= 104message 只包含小写英文字母和 ' ' 。1 <= limit <= 104
解法
方法一：枚举分段数量 + 模拟
我们设字符串 message 的长度为 $n$，分段数量为 $k$。
根据题意，如果 $k \gt n$，表示我们可以将字符串划分成超过 $n$ 段，由于字符串长度仅为 $n$，若划分成超过 $n$ 段必然导致有部分段的长度为 $0$，可以删去。因此，我们只需要将 $k$ 的取值范围限制在 $[1,.. n]$ 即可。
从小到大枚举分段数量 $k$，记所有分段中 $a$ 段的长度为 $sa$，所有分段中 $b$ 段的长度为 $sb$，所有分段中符号（包括尖括号和斜杠）的长度为 $sc$。
那么 $sa$ 的值为 ${\textstyle \sum_{j=1}^{k}} len(s_j)$，可以直接通过前缀和求出；而 $sb$ 的值为 $len(str(k)) \times k$；另外 $sc$ 的值为 $3 \times k$。
因此，所有分段剩余可填充的字符数为 $limit\times k - (sa + sb + sc)$，如果该值大于等于 $n$ 则说明可以将字符串划分成 $k$ 段，直接构造答案返回即可。
时间复杂度 $O(n\times \log n)$，其中 $n$ 为字符串 message 的长度。忽略答案的空间消耗，空间复杂度 $O(1)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | class Solution:
def splitMessage(self, message: str, limit: int) -> List[str]:
n = len(message)
sa = 0
for k in range(1, n + 1):
sa += len(str(k))
sb = len(str(k)) * k
sc = 3 * k
if limit * k - (sa + sb + sc) >= n:
ans = []
i = 0
for j in range(1, k + 1):
tail = f'<{j}/{k}>'
t = message[i : i + limit - len(tail)] + tail
ans.append(t)
i += limit - len(tail)
return ans
return []
|
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 | class Solution {
public String[] splitMessage(String message, int limit) {
int n = message.length();
int sa = 0;
String[] ans = new String[0];
for (int k = 1; k <= n; ++k) {
int lk = (k + "").length();
sa += lk;
int sb = lk * k;
int sc = 3 * k;
if (limit * k - (sa + sb + sc) >= n) {
int i = 0;
ans = new String[k];
for (int j = 1; j <= k; ++j) {
String tail = String.format("<%d/%d>", j, k);
String t = message.substring(i, Math.min(n, i + limit - tail.length())) + tail;
ans[j - 1] = t;
i += limit - tail.length();
}
break;
}
}
return ans;
}
}
|
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 | class Solution {
public:
vector<string> splitMessage(string message, int limit) {
int n = message.size();
int sa = 0;
vector<string> ans;
for (int k = 1; k <= n; ++k) {
int lk = to_string(k).size();
sa += lk;
int sb = lk * k;
int sc = 3 * k;
if (k * limit - (sa + sb + sc) >= n) {
int i = 0;
for (int j = 1; j <= k; ++j) {
string tail = "<" + to_string(j) + "/" + to_string(k) + ">";
string t = message.substr(i, limit - tail.size()) + tail;
ans.emplace_back(t);
i += limit - tail.size();
}
break;
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 | func splitMessage(message string, limit int) (ans []string) {
n := len(message)
sa := 0
for k := 1; k <= n; k++ {
lk := len(strconv.Itoa(k))
sa += lk
sb := lk * k
sc := 3 * k
if limit*k-(sa+sb+sc) >= n {
i := 0
for j := 1; j <= k; j++ {
tail := "<" + strconv.Itoa(j) + "/" + strconv.Itoa(k) + ">"
t := message[i:min(i+limit-len(tail), n)] + tail
ans = append(ans, t)
i += limit - len(tail)
}
break
}
}
return
}
|