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 <= 105
s 僅包含小寫英文字母。
問題分析：
根據題目的描述，從0號字符開始向后拓展構建新段，在拓展時，只要該段在之前未出現過，就將其加入新段列表，并從下一個下標開始構建新段，所以從一個下標開始找出一個新段是解決問題的關鍵，為此設計函數struct_new_paragraph(i,s,pars)，其功能是從下標i開始在字符串s中拓展新段，并將新段加入新段列表pars中，函數返回構建下一個新段的起始位置和本次生成的新段列表，這樣可以反復調用本函數以拓展后續的新段。
主程序根據輸入的字符串s，從索引號0開始利用struct_new_paragraph(i,s,pars)函數拓展新段，只要返回的起始位置小于字符串s的長度n，就可以不斷拓展，最后將新段列表輸出，即是問題的解。
程序如下：
#通過起始位置i、原字符串s和新段列表pars構造新段，返回下一個新段的起始位置和本次生成的新段列表
def struct_new_paragraph(i,s,pars):n=len(s)# j用于控制結束位置，所以當起位置i取到n-1時，j要取到n+1for j in range(i+1,n+1):a=s[i:j]print('截取字符串:',a)if a not in pars:pars.append(a)print(f'新段起始位置{j},新段列表{pars}')return j,parselse:print(f'{a}已經在新段列表中')continueelse:print('j,pars:',n,pars)return n,pars#主程序
s=input('pls input s=')
pars=[]
n=len(s)
print('新段起始位置為0，新段列表為[]')
(i,pars)=struct_new_paragraph(0,s,pars)
while i<n:i, pars = struct_new_paragraph(i, s, pars)
print(f'起始位置索引號{i}已經超過字符串{s}的最大索引號{n-1}')
print(f'最終輸出新段列表為{pars}')運行實例一
pls input s=abaacd
新段起始位置為0，新段列表為[]
截取字符串: a
新段起始位置1,新段列表['a']
截取字符串: b
新段起始位置2,新段列表['a', 'b']
截取字符串: a
a已經在新段列表中
截取字符串: aa
新段起始位置4,新段列表['a', 'b', 'aa']
截取字符串: c
新段起始位置5,新段列表['a', 'b', 'aa', 'c']
截取字符串: d
新段起始位置6,新段列表['a', 'b', 'aa', 'c', 'd']
起始位置索引號6已經超過字符串abaacd的最大索引號5
最終輸出新段列表為['a', 'b', 'aa', 'c', 'd']
運行實例二
pls input s=bbbbbb
新段起始位置為0，新段列表為[]
截取字符串: b
新段起始位置1,新段列表['b']
截取字符串: b
b已經在新段列表中
截取字符串: bb
新段起始位置3,新段列表['b', 'bb']
截取字符串: b
b已經在新段列表中
截取字符串: bb
bb已經在新段列表中
截取字符串: bbb
新段起始位置6,新段列表['b', 'bb', 'bbb']
起始位置索引號6已經超過字符串bbbbbb的最大索引號5
最終輸出新段列表為['b', 'bb', 'bbb']
運行實例三
pls input s=abbcccd
新段起始位置為0，新段列表為[]
截取字符串: a
新段起始位置1,新段列表['a']
截取字符串: b
新段起始位置2,新段列表['a', 'b']
截取字符串: b
b已經在新段列表中
截取字符串: bc
新段起始位置4,新段列表['a', 'b', 'bc']
截取字符串: c
新段起始位置5,新段列表['a', 'b', 'bc', 'c']
截取字符串: c
c已經在新段列表中
截取字符串: cd
新段起始位置7,新段列表['a', 'b', 'bc', 'c', 'cd']
起始位置索引號7已經超過字符串abbcccd的最大索引號6
最終輸出新段列表為['a', 'b', 'bc', 'c', 'cd']
理清處理問題的邏輯順序，合理分割其中的處理步驟，轉換成對應的函數，問題必將容易解決。
)
