2468-根据限制分割消息

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:30 2023-09-13 16:06:30 Updated    

给你一个字符串 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

视频讲解 已出炉，欢迎点赞三连，在评论区分享你对这场双周赛的看法~

设分割个数为 i，它能「容纳」多长的 message？

核心思路：设 message 的长度为 n。枚举分割个数 i，不断增大容量 cap，直到 cap} \ge n 为止，就可以分割了。

[sol1-Python3]
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
class Solution:
    def splitMessage(self, message: str, limit: int) -> List[str]:
        i = cap = 0
        while True:
            i += 1
            if i < 10:
                tail_len = 5  # 结尾的长度
            elif i < 100:
                if i == 10: cap -= 9  # 前面的结尾的长度都 +1，那么容量就要减小
                tail_len = 7
            elif i < 1000:
                if i == 100: cap -= 99
                tail_len = 9
            else:
                if i == 1000: cap -= 999
                tail_len = 11
            if tail_len >= limit: return []  # cap 无法增大，寄
            cap += limit - tail_len
            if cap < len(message): continue  # 容量没有达到，继续枚举

            ans, k = [], 0
            for j in range(1, i + 1):
                tail = f"<{j}/{i}>"
                if j == i:
                    ans.append(message[k:] + tail)
                else:
                    m = limit - len(tail)
                    ans.append(message[k: k + m] + tail)
                    k += m
            return ans
[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
33
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;
        }
    }
}
[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
class Solution {
public:
    vector<string> splitMessage(string message, int limit) {
        int 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 {}; // cap 无法增大，寄
            cap += limit - tail_len;
            if (cap < n) continue; // 容量没有达到，继续枚举

            vector<string> ans(i);
            for (int j = 0, k = 0; j < i; ++j) {
                string tail = "<" + to_string(j + 1) + "/" + to_string(i) + ">";
                if (j == i - 1) ans[j] = message.substr(k) + tail;
                else {
                    int m = limit - tail.length();
                    ans[j] = message.substr(k, m) + tail;
                    k += m;
                }
            }
            return ans;
        }
    }
};
[sol1-Go]
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
func splitMessage(message string, limit int) []string {
	for i, cap, tailLen := 1, 0, 0; ; i++ {
		if i < 10 {
			tailLen = 5 // 结尾的长度
		} else if i < 100 {
			if i == 10 { cap -= 9 } // 前面的结尾的长度都 +1，那么容量就要减小
			tailLen = 7
		} else if i < 1000 {
			if i == 100 { cap -= 99 }
			tailLen = 9
		} else {
			if i == 1000 { cap -= 999 }
			tailLen = 11
		}
		if tailLen >= limit { return nil } // cap 无法增大，寄
		cap += limit - tailLen
		if cap < len(message) { continue } // 容量没有达到，继续枚举

		ans := make([]string, i)
		for j := range ans {
			tail := fmt.Sprintf("<%d/%d>", j+1, i)
			if j == i-1 {
				ans[j] = message + tail
			} else {
				m := limit - len(tail)
				ans[j] = message[:m] + tail
				message = message[m:]
			}
		}
		return ans
	}
}

复杂度分析

  • 时间复杂度：O(n\log n)，其中 n 为 message 的长度。构造答案需要 O(n\log n) 的时间。
  • 空间复杂度：O(1)，返回值的空间不计入。
 Comments
On this page
2468-根据限制分割消息