3597. 分割字符串

题目描述

给你一个字符串 s，按照以下步骤将其分割为 互不相同的段 ：

从下标 0 开始构建一个段。
逐字符扩展当前段，直到该段之前未曾出现过。
只要当前段是唯一的，就将其加入段列表，标记为已经出现过，并从下一个下标开始构建新的段。
重复上述步骤，直到处理完整个字符串 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"]

因此，最终输出为 ["a", "b", "bc", "c", "cc", "d"]。

示例 2：

输入： s = "aaaa"

输出： ["a","aa"]

解释：

下标	添加后的段	已经出现过的段	当前段是否已经出现过？	新段	更新后已经出现过的段
0	"a"	[]	否	""	["a"]
1	"a"	["a"]	是	"a"	["a"]
2	"aa"	["a"]	否	""	["a", "aa"]
3	"a"	["a", "aa"]	是	"a"	["a", "aa"]

因此，最终输出为 ["a", "aa"]。

提示：

1 <= s.length <= 10⁵
s 仅包含小写英文字母。

解法

方法一：哈希表 + 模拟

我们可以用一个哈希表 \(\textit{vis}\) 来记录已经出现过的段。然后我们遍历字符串 \(s\)，逐字符构建当前段 \(t\)，直到该段之前未曾出现过。每当我们构建出一个新的段时，就将其加入到结果列表中，并将其标记为已经出现过。

遍历结束后，返回结果列表即可。

时间复杂度 \(O(n \times \sqrt{n})\)，空间复杂度 \(O(n)\)，其中 \(n\) 是字符串 \(s\) 的长度。

Python3JavaC++GoTypeScript

class Solution:
    def partitionString(self, s: str) -> List[str]:
        vis = set()
        ans = []
        t = ""
        for c in s:
            t += c
            if t not in vis:
                vis.add(t)
                ans.append(t)
                t = ""
        return ans

class Solution {
    public List<String> partitionString(String s) {
        Set<String> vis = new HashSet<>();
        List<String> ans = new ArrayList<>();
        String t = "";
        for (char c : s.toCharArray()) {
            t += c;
            if (vis.add(t)) {
                ans.add(t);
                t = "";
            }
        }
        return ans;
    }
}

class Solution {
public:
    vector<string> partitionString(string s) {
        unordered_set<string> vis;
        vector<string> ans;
        string t = "";
        for (char c : s) {
            t += c;
            if (!vis.contains(t)) {
                vis.insert(t);
                ans.push_back(t);
                t = "";
            }
        }
        return ans;
    }
};

func partitionString(s string) (ans []string) {
    vis := make(map[string]bool)
    t := ""
    for _, c := range s {
        t += string(c)
        if !vis[t] {
            vis[t] = true
            ans = append(ans, t)
            t = ""
        }
    }
    return
}

function partitionString(s: string): string[] {
    const vis = new Set<string>();
    const ans: string[] = [];
    let t = '';
    for (const c of s) {
        t += c;
        if (!vis.has(t)) {
            vis.add(t);
            ans.push(t);
            t = '';
        }
    }
    return ans;
}

方法二：字符串哈希 + 哈希表 + 模拟

我们可以使用字符串哈希来加速段的查找。具体地，我们可以为每个段计算一个哈希值，并将其存储在一个哈希表中。这样，我们就可以在常数时间内判断一个段是否已经出现过。

具体地，我们首先根据字符串 \(s\) 创建一个字符串哈希类 \(\textit{Hashing}\)，该类支持计算字符串的哈希值。然后，我们遍历字符串 \(s\)，用两个指针 \(l\) 和 \(r\) 来表示当前段的起始和结束位置（下标从 \(1\) 开始）。每次扩展 \(r\)，我们计算当前段的哈希值 \(x\)，如果该哈希值不在哈希表中，则将其加入结果列表，并将其哈希值标记为已经出现过。否则，我们继续扩展 \(r\)，直到找到一个新的段。