【算法题】2468. 根据限制分割消息

2023-08-04  本文已影响0人  程序员小2

题目:

给你一个字符串 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>"]
解释:
在给定限制下,字符串可以分成两个部分:

提示:

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

上一篇下一篇

猜你喜欢

热点阅读