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

解法

方法一：枚举分段数量 + 模拟

思考

每段带后缀 \(<j/k>\)，总长度上限 \(limit\)。\(n \le 10^4\)，从 \(k=1\) 枚举段数：所有下标数字、总段数字与三个符号的长度可 \(O(1)\) 累加。剩余容量 \(\ge n\) 时按 \(limit\) 切正文并接上后缀。

我们设字符串 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)\)。

Python3JavaC++Go

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 []

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;
    }
}

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;
    }
};

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
}

2468. 根据限制分割消息

题目描述

解法

方法一：枚举分段数量 + 模拟

评论