763_(划分字母区间)Partition Labels

Seawolf

763_(划分字母区间)Partition Labels

1 问题描述、输入输出与样例

1.1 问题描述

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一个字母只会出现在其中的一个片段。

返回一个表示每个字符串片段的长度的列表。

注意:

S的长度在[1, 500]之间。
S只包含小写字母'a'到'z'。
1.2 输入与输出

输入：

string S:带划分的字符串 S
输出：

vector< int>:划分为尽可能多的片段， 每个字符串片段的长度的列表
1.3 样例

1.3.1 样例1

输入: S = "ababcbacadefegdehijhklij"

输出: [9,7,8]

解释:划分结果为 "ababcbaca", "defegde", "hijhklij"。

每个字母最多出现在一个片段中。像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。

S = "ababcbacadefegdehijhklij"

lst = []

memo = []

memo1 = []

for i in S:

    lst.append(i)

def get_head(L):

    if L == []:

        return []

    else:

        return L[0]

def get_tail(L):


    if L ==[]:

        return []

    else:
        return L[1:]

def member(X,L):

    if L ==[]:
        return False

    if X == get_head(L):

        return True
    else:

        return member(X,get_tail(L))

def length(L):

    if L == []:

        return 0

    else:
        return 1 + length(get_tail(L))

def split(L):

    len = length(L)

    for i in range(len):

        start = 100

        end = 0

        temp = L[i]

        for j in range(len):

            if j < start and L[i] == L[j]:

                start = j

            if member(temp, L[j:]):

                if j > end:

                    end = j

        memo.append([start,end])

def print_all():

    for i in range(length(memo)):

        small = memo[i][0]

        big = memo[i][1]

        for j in range(length(memo)):

            if not (memo[j][1]< small or memo[j][0] > big):

                if memo[j][0] < small:

                    small =  memo[j][0]

                elif memo[j][1] > big:

                    big = memo[j][1]

        if [small,big+1] not in memo1:

            memo1.append([small,big+1])


    for i in range(length(memo1)):

        print(S[memo1[i][0]:memo1[i][1]])


split(lst)
print_all()

output:

ababcbaca
defegde
hijhklij