from typing import List
# 這道題使用雙指標的方法寫的，
# 兩個指標定義開頭和結束，首先找到尾指標和頭指標相同的字符，（注意要從后邊尋找）
# 然后判斷兩個指標中間的字符在字串中是否存在其他的相同字符，
class Solution:
def partitionLabels(self, S: str) -> List[int]:
# 定義串列，用來存放分段的字串長度
self.str_list = []
# 字串為慷訓傳空串列
if len(S) == 0:return []
# 先定義兩個指標
index1,index2 = 0,len(S) - 1
# 當尋找到分段字串的長度等于字串長度時就退出回圈
while sum(self.str_list) < len(S):
# 首先找到尾指標和頭指標相同的字符
while S[index2] != S[index1]:
index2 -= 1
index = index1
# 然后判斷index1 - index2 中間的字符在S中的其他地方有沒有出現
while index1 != index2:
# 如果有出現，就接著從后邊遍歷尾指標，找到那個和當前的字符相同的
if S[index1] in S[index2:]:
index2 = len(S) - 1
while S[index2] != S[index1]:
index2 -= 1
index1 += 1
# 將分段的字串長度添加進去串列，
self.str_list.append(index2 - index + 1)
# 改變idnex1和index2的值，重新回圈
index1,index2 = index2 + 1,len(S) - 1
return self.str_list
A = Solution()
print(A.partitionLabels("ababcbacadefegdehijhklij"))
print(A.partitionLabels("aebbedaddc"))
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/59857.html
標籤：Python
上一篇：Django3.1 版本說明