Medium

题目描述

给定一个字符串 s，按照以下步骤将其分割成唯一的段：

  1. 从索引 0 开始构建一个段。
  2. 逐字符扩展当前段，直到当前段之前没有出现过。
  3. 一旦段是唯一的，将其添加到段列表中，标记为已见，并从下一个索引开始新段。
  4. 重复直到到达 s 的末尾。

返回字符串数组 segments，其中 segments[i] 是创建的第 i 个段。

示例 1：

输入：s = "abbccccd"
输出：["a","b","bc","c","cc","d"]

解释：

索引添加后的段已见段当前段之前见过？新段更新的已见段
0“a”[]否""[“a”]
1“b”[“a”]否""[“a”, “b”]
2“b”[“a”, “b”]是“b”[“a”, “b”]
3“bc”[“a”, “b”]否""[“a”, “b”, “bc”]
4“c”[“a”, “b”, “bc”]否""[“a”, “b”, “bc”, “c”]
5“c”[“a”, “b”, “bc”, “c”]是“c”[“a”, “b”, “bc”, “c”]
6“cc”[“a”, “b”, “bc”, “c”]否""[“a”, “b”, “bc”, “c”, “cc”]
7“d”[“a”, “b”, “bc”, “c”, “cc”]否""[“a”, “b”, “bc”, “c”, “cc”, “d”]

示例 2：

输入：s = "aaaa"
输出：["a","aa"]

约束条件：

  • 1 <= s.length <= 10^5
  • s 只包含小写英文字母。

解题思路

这道题要求我们根据特定规则分割字符串：从左到右扫描，逐步构建当前段，直到当前段是之前没有出现过的唯一段为止，然后开始新的段。

解题思路：

  1. 模拟过程：按照题目描述的步骤进行模拟，使用哈希集合记录已经出现过的段。

  2. 贪心策略：从每个起始位置开始，尽可能构建最短的唯一段。这样可以确保后续有更多选择空间。

  3. 具体实现：

    • 使用哈希集合 seen 记录已经出现过的段
    • 维护当前段的起始位置 start
    • 从 start 开始逐个字符扩展，检查当前段是否在 seen 中
    • 如果当前段不在 seen 中，说明找到了唯一段，加入结果并更新 seen
    • 继续处理下一个段

  4. 时间复杂度优化：虽然看起来有嵌套循环，但每个字符最多被访问常数次，总体时间复杂度是线性的。

这个方法直接模拟了题目描述的过程，思路清晰，实现简单。

代码实现

class Solution {
public:
    vector<string> partitionString(string s) {
        vector<string> result;
        unordered_set<string> seen;
        int n = s.length();
        int start = 0;
        
        while (start < n) {
            for (int end = start + 1; end <= n; end++) {
                string segment = s.substr(start, end - start);
                if (seen.find(segment) == seen.end()) {
                    result.push_back(segment);
                    seen.insert(segment);
                    start = end;
                    break;
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def partitionString(self, s: str) -> List[str]:
        result = []
        seen = set()
        start = 0
        n = len(s)
        
        while start < n:
            for end in range(start + 1, n + 1):
                segment = s[start:end]
                if segment not in seen:
                    result.append(segment)
                    seen.add(segment)
                    start = end
                    break
        
        return result

public class Solution {
    public IList<string> PartitionString(string s) {
        var result = new List<string>();
        var seen = new HashSet<string>();
        int start = 0;
        int n = s.Length;
        
        while (start < n) {
            for (int end = start + 1; end <= n; end++) {
                string segment = s.Substring(start, end - start);
                if (!seen.Contains(segment)) {
                    result.Add(segment);
                    seen.Add(segment);
                    start = end;
                    break;
                }
            }
        }
        
        return result;
    }
}

/**
 * @param {string} s
 * @return {string[]}
 */
var partitionString = function(s) {
    const result = [];
    const seen = new Set();
    let start = 0;
    const n = s.length;
    
    while (start < n) {
        for (let end = start + 1; end <= n; end++) {
            const segment = s.substring(start, end);
            if (!seen.has(segment)) {
                result.push(segment);
                seen.add(segment);
                start = end;
                break;
            }
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n²)最坏情况下每个位置都要扫描到字符串末尾，但平均情况下接近线性
空间复杂度O(n)哈希集合存储所有唯一段，最坏情况下可能有 O(n) 个段