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 个部分每个取 2 个字符来完成 message 的拆分。
在这个例子中，每个部分包括最后一个都有长度 9。
可以证明不可能将 message 拆分成少于 14 个部分。

示例 2：

输入：message = "short message", limit = 15
输出：["short mess<1/2>","age<2/2>"]
解释：
在给定的约束下，字符串可以拆分为两部分：
- 第一部分包含前 10 个字符，长度为 15。
- 下一部分包含最后 3 个字符，长度为 8。

约束条件：

  • 1 <= message.length <= 10^4
  • message 只包含小写英文字母和 ' '
  • 1 <= limit <= 10^4

解题思路

这道题的核心是确定拆分的总部分数，然后验证能否按此部分数成功拆分。

解题思路：

  1. 枚举总部分数：从1开始枚举可能的总部分数 parts，对于每个部分数检查是否能成功拆分。

  2. 计算后缀长度：对于总部分数 parts，每个部分的后缀格式为 <i/parts>，其中 i 是部分索引。后缀长度为 len(str(i)) + len(str(parts)) + 3（包括 <、/、>）。

  3. 验证可行性：

    • 计算每个部分可用于存放消息内容的空间：limit - 后缀长度
    • 如果某个部分的可用空间 ≤ 0，则当前部分数不可行
    • 计算所有部分的总可用空间，如果小于消息长度，则不可行

  4. 构造结果：一旦找到最小可行的部分数，按顺序构造每个部分，将消息内容和对应后缀组合。

关键优化：

  • 按部分数从小到大枚举，找到第一个可行解就是最优解
  • 提前检查总可用空间，避免不必要的计算

时间复杂度主要取决于总部分数的上界，在最坏情况下约为 O(√n)，其中 n 为消息长度。

代码实现

class Solution {
public:
    vector<string> splitMessage(string message, int limit) {
        int n = message.length();
        
        for (int parts = 1; parts <= n; parts++) {
            // 计算是否可以用 parts 个部分来分割
            int totalAvailable = 0;
            bool valid = true;
            
            for (int i = 1; i <= parts; i++) {
                int suffixLen = to_string(i).length() + to_string(parts).length() + 3; // <i/parts>
                int available = limit - suffixLen;
                if (available <= 0) {
                    valid = false;
                    break;
                }
                totalAvailable += available;
            }
            
            if (!valid || totalAvailable < n) continue;
            
            // 构造结果
            vector<string> result;
            int pos = 0;
            
            for (int i = 1; i <= parts; i++) {
                string suffix = "<" + to_string(i) + "/" + to_string(parts) + ">";
                int available = limit - suffix.length();
                string part = message.substr(pos, min(available, n - pos)) + suffix;
                result.push_back(part);
                pos += available;
            }
            
            return result;
        }
        
        return {};
    }
};

class Solution:
    def splitMessage(self, message: str, limit: int) -> List[str]:
        n = len(message)
        
        for parts in range(1, n + 1):
            # 计算是否可以用 parts 个部分来分割
            total_available = 0
            valid = True
            
            for i in range(1, parts + 1):
                suffix_len = len(str(i)) + len(str(parts)) + 3  # <i/parts>
                available = limit - suffix_len
                if available <= 0:
                    valid = False
                    break
                total_available += available
            
            if not valid or total_available < n:
                continue
            
            # 构造结果
            result = []
            pos = 0
            
            for i in range(1, parts + 1):
                suffix = f"<{i}/{parts}>"
                available = limit - len(suffix)
                part = message[pos:pos + min(available, n - pos)] + suffix
                result.append(part)
                pos += available
            
            return result
        
        return []

public class Solution {
    public string[] SplitMessage(string message, int limit) {
        int n = message.Length;
        
        for (int parts = 1; parts <= n; parts++) {
            // 计算是否可以用 parts 个部分来分割
            int totalAvailable = 0;
            bool valid = true;
            
            for (int i = 1; i <= parts; i++) {
                int suffixLen = i.ToString().Length + parts.ToString().Length + 3; // <i/parts>
                int available = limit - suffixLen;
                if (available <= 0) {
                    valid = false;
                    break;
                }
                totalAvailable += available;
            }
            
            if (!valid || totalAvailable < n) continue;
            
            // 构造结果
            var result = new List<string>();
            int pos = 0;
            
            for (int i = 1; i <= parts; i++) {
                string suffix = $"<{i}/{parts}>";
                int available = limit - suffix.Length;
                string part = message.Substring(pos, Math.Min(available, n - pos)) + suffix;
                result.Add(part);
                pos += available;
            }
            
            return result.ToArray();
        }
        
        return new string[0];
    }
}

var splitMessage = function(message, limit) {
    const n = message.length;
    
    for (let parts = 1; parts <= n; parts++) {
        // 计算是否可以用 parts 个部分来分割
        let totalAvailable = 0;
        let valid = true;
        
        for (let i = 1; i <= parts; i++) {
            const suffixLen = i.toString().length + parts.toString().length + 3; // <i/parts>
            const available = limit - suffixLen;
            if (available <= 0) {
                valid = false;
                break;
            }
            totalAvailable += available;
        }
        
        if (!valid || totalAvailable < n) continue;
        
        // 构造结果
        const result = [];
        let pos = 0;
        
        for (let i = 1; i <= parts; i++) {
            const suffix = `<${i}/${parts}>`;
            const available = limit - suffix.length;
            const part = message.substring(pos, pos + Math.min(available, n - pos)) + suffix;
            result.push(part);
            pos += available;
        }
        
        return result;
    }
    
    return [];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(k²) 其中 k 是最终的部分数，最坏情况下 k = O(√n)
空间复杂度O(k) 用于存储结果数组

相关题目