【算法题】2468. 根据限制分割消息
题目:
给你一个字符串 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 <= 104
message 只包含小写英文字母和 ' ' 。
1 <= limit <= 104
java代码:
class Solution {
public String[] splitMessage(String message, int limit) {
var n = message.length();
for (int i = 1, cap = 0, tail_len; ; ++i) {
if (i < 10) tail_len = 5; // 结尾的长度
else if (i < 100) {
if (i == 10) cap -= 9; // 前面的结尾的长度都 +1,那么容量就要减小
tail_len = 7;
} else if (i < 1000) {
if (i == 100) cap -= 99;
tail_len = 9;
} else {
if (i == 1000) cap -= 999;
tail_len = 11;
}
if (tail_len >= limit) return new String[]{}; // cap 无法增大,寄
cap += limit - tail_len;
if (cap < n) continue; // 容量没有达到,继续枚举
var ans = new String[i];
for (int j = 0, k = 0; j < i; ++j) {
var tail = "<" + (j + 1) + "/" + i + ">";
if (j == i - 1) ans[j] = message.substring(k) + tail;
else {
var m = limit - tail.length();
ans[j] = message.substring(k, k + m) + tail;
k += m;
}
}
return ans;
}
}
}