根据限制分割消息

难度: Hard

给你一个字符串 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 <= 10⁴
message 只包含小写英文字母和 ' ' 。
1 <= limit <= 10⁴

Submission

运行时间: 71 ms

内存: 18.3 MB

import math


class Solution:
    def splitMessage(self, message: str, limit: int) -> List[str]:
        leng = len(message)
        num = 0
        n = 0
        for i in range(4):
            if i == 0:
                if limit <= 5:
                    return []
                n = math.ceil(leng / (limit - 5))
                if n < 10:
                    num = i
                    break
            elif i == 1:
                if limit <= 7:
                    return []
                n = math.ceil((leng - 9 * (limit - 6)) / (limit - 7) + 9)
                if n < 100:
                    num = i
                    break
            elif i == 2:
                if limit <= 9:
                    return []
                n = math.ceil(
                    (leng - 9 * (limit - 7) - 90 * (limit - 8)) / (limit - 9) + 99
                )
                if n < 1000:
                    num = i
                    break
            else:
                if limit <= 11:
                    return []
                n = math.ceil(
                    999
                    + (leng - (limit - 8) * 9 - (limit - 9) * 90 - (limit - 10) * 900)
                    / (limit - 11)
                )
                if n < 10000:
                    num = i
                    break
        print(leng, num, n)
        mess_list = []
        str_ = "/" + str(n) + ">"
        j = 0
        if num == 0:
            s_l = limit - 5
            for i in range(1, n + 1):
                if i != n:
                    tmp_str = message[j:s_l] + "<" + str(i) + str_
                    j = s_l
                    s_l += limit - 5
                else:
                    tmp_str = message[j:] + "<" + str(i) + str_
                mess_list.append(tmp_str)
        elif num == 1:
            s_l = limit - 6
            for i in range(1, n + 1):
                if i < 10:
                    tmp_str = message[j:s_l] + "<" + str(i) + str_
                    j = s_l
                    s_l += limit - 6
                elif i < n:
                    s_l -= 1
                    tmp_str = message[j:s_l] + "<" + str(i) + str_
                    j = s_l
                    s_l += limit - 7 + 1
                else:
                    tmp_str = message[j:] + "<" + str(i) + str_
                mess_list.append(tmp_str)
                # print(j, s_l)
        elif num == 2:
            s_l = limit - 7
            for i in range(1, n + 1):
                if i < 10:
                    tmp_str = message[j:s_l] + "<" + str(i) + str_
                    j = s_l
                    s_l += limit - 7
                elif i < 100:
                    s_l -= 1
                    tmp_str = message[j:s_l] + "<" + str(i) + str_
                    j = s_l
                    s_l += limit - 8 + 1
                elif i < n:
                    s_l -= 2
                    tmp_str = message[j:s_l] + "<" + str(i) + str_
                    j = s_l
                    s_l += limit - 9 + 2
                else:
                    tmp_str = message[j:] + "<" + str(i) + str_
                mess_list.append(tmp_str)
        else:
            s_l = limit - 8
            for i in range(1, n + 1):
                if i < 10:
                    tmp_str = message[j:s_l] + "<" + str(i) + str_
                    j = s_l
                    s_l += limit - 8
                elif i < 100:
                    s_l -= 1
                    tmp_str = message[j:s_l] + "<" + str(i) + str_
                    j = s_l
                    s_l += limit - 9 + 1
                elif i < 1000:
                    s_l -= 2
                    tmp_str = message[j:s_l] + "<" + str(i) + str_
                    j = s_l
                    s_l += limit - 10 + 2
                elif i < n:
                    s_l -= 3
                    tmp_str = message[j:s_l] + "<" + str(i) + str_
                    j = s_l
                    s_l += limit - 11 + 3
                else:
                    tmp_str = message[j:] + "<" + str(i) + str_
                mess_list.append(tmp_str)
        return mess_list

Explain

此题解尝试通过一系列计算来确定如何有效分割字符串，以使每段的长度等于或小于给定的limit。解法考虑了每个部分结尾处的索引标记所需的额外字符数。不同的索引长度（1位、2位、3位或4位数字）会导致每部分可用于实际消息的字符数不同。题解先通过循环遍历四种情况来确定最少需要的部分数n。然后基于所需部分数n和每个部分的结尾长度，对消息进行分割。根据分割的部分数和每部分结尾所需的字符数，调整每次截取的字符串长度，确保每个部分满足长度要求。如果长度不够分配到每一部分，将返回空数组。

时间复杂度: O(n)

空间复杂度: O(n)

import math


class Solution:
    def splitMessage(self, message: str, limit: int) -> List[str]:
        leng = len(message)
        num = 0
        n = 0
        for i in range(4):
            if i == 0:
                if limit <= 5:
                    return []
                n = math.ceil(leng / (limit - 5))
                if n < 10:
                    num = i
                    break
            elif i == 1:
                if limit <= 7:
                    return []
                n = math.ceil((leng - 9 * (limit - 6)) / (limit - 7) + 9)
                if n < 100:
                    num = i
                    break
            elif i == 2:
                if limit <= 9:
                    return []
                n = math.ceil((leng - 9 * (limit - 7) - 90 * (limit - 8)) / (limit - 9) + 99)
                if n < 1000:
                    num = i
                    break
            else:
                if limit <= 11:
                    return []
                n = math.ceil(999 + (leng - (limit - 8) * 9 - (limit - 9) * 90 - (limit - 10) * 900) / (limit - 11))
                if n < 10000:
                    num = i
                    break
        print(leng, num, n)
        mess_list = []
        str_ = "/" + str(n) + ">"
        j = 0
        if num == 0:
            s_l = limit - 5
            for i in range(1, n + 1):
                if i != n:
                    tmp_str = message[j:s_l] + "<" + str(i) + str_
                    j = s_l
                    s_l += limit - 5
                else:
                    tmp_str = message[j:] + "<" + str(i) + str_
                mess_list.append(tmp_str)
        elif num == 1:
            s_l = limit - 6
            for i in range(1, n + 1):
                if i < 10:
                    tmp_str = message[j:s_l] + "<" + str(i) + str_
                    j = s_l
                    s_l += limit - 6
                elif i < n:
                    s_l -= 1
                    tmp_str = message[j:s_l] + "<" + str(i) + str_
                    j = s_l
                    s_l += limit - 7 + 1
                else:
                    tmp_str = message[j:] + "<" + str(i) + str_
                mess_list.append(tmp_str)
        elif num == 2:
            s_l = limit - 7
            for i in range(1, n + 1):
                if i < 10:
                    tmp_str = message[j:s_l] + "<" + str(i) + str_
                    j = s_l
                    s_l += limit - 7
                elif i < 100:
                    s_l -= 1
                    tmp_str = message[j:s_l] + "<" + str(i) + str_
                    j = s_l
                    s_l += limit - 8 + 1
                elif i < n:
                    s_l -= 2
                    tmp_str = message[j:s_l] + "<" + str(i) + str_
                    j = s_l
                    s_l += limit - 9 + 2
                else:
                    tmp_str = message[j:] + "<" + str(i) + str_
                mess_list.append(tmp_str)
        else:
            s_l = limit - 8
            for i in range(1, n + 1):
                if i < 10:
                    tmp_str = message[j:s_l] + "<" + str(i) + str_
                    j = s_l
                    s_l += limit - 8
                elif i < 100:
                    s_l -= 1
                    tmp_str = message[j:s_l] + "<" + str(i) + str_
                    j = s_l
                    s_l += limit - 9 + 1
                elif i < 1000:
                    s_l -= 2
                    tmp_str = message[j:s_l] + "<" + str(i) + str_
                    j = s_l
                    s_l += limit - 10 + 2
                elif i < n:
                    s_l -= 3
                    tmp_str = message[j:s_l] + "<" + str(i) + str_
                    j = s_l
                    s_l += limit - 11 + 3
                else:
                    tmp_str = message[j:] + "<" + str(i) + str_
                mess_list.append(tmp_str)
        return mess_list

Explore

在给定的解决方案中，每个消息段结束时需要添加一个特定格式的编号（例如'<1>'），这个编号的长度取决于编号数字的位数。因为每个段的总长度（包括文本和编号）不能超过限制`limit`，所以必须从可用于文本的字符数中减去编号的字符数。随着编号位数的增加，可用于文本的字符数相应减少，因此我们需要根据编号的位数调整每段的文本长度。

解决方案通过计算每种位数编号所需的额外字符数，并相应地调整字符串截取的长度来确保。例如，如果编号为一位数，那么除了本身的编号外，还需要额外的字符来形成如'<1>'的格式。算法预先计算出每种情况下的最大编号长度，并在循环中不断调整截取长度，以确保包括编号在内的总长度不超过设定的限制`limit`。

这些特定的`limit`值是基于分段结束的标记最小可能长度确定的。例如，如果分段结束标记为'<1>'，至少需要5个字符。如果`limit`值小于这个最小长度，那么即使是最短的标记也无法满足，因此直接返回空数组。这是为了避免在构造消息段时因空间不足而无法满足要求。

不同的循环是为了处理随着消息段数增加而可能变化的编号位数。随着序号的增加，编号的位数可能从1位变成2位、3位，甚至更多，这直接影响每段可以包含的文字数量。使用循环可以动态地调整每段的长度，以适应编号长度的变化。这种方法虽然在理论上增加了计算复杂度，但提供了一种灵活处理不同情况的有效方式，尤其是在需要精确控制每段长度时。