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" 的划分是错误的，因为划分的片段数较少。

1. S = "ababcbacadefegdehijhklij"
   
2. 
   
3. lst = []
   
4. 
   
5. memo = []
   
6. 
   
7. memo1 = []
   
8. 
   
9. for i in S:
   
10. 
    
11.     lst.append(i)
    
12. 
    
13. def get_head(L):
    
14. 
    
15.     if L == []:
    
16. 
    
17.         return []
    
18. 
    
19.     else:
    
20. 
    
21.         return L[0]
    
22. 
    
23. def get_tail(L):
    
24. 
    
25. 
    
26.     if L ==[]:
    
27. 
    
28.         return []
    
29. 
    
30.     else:
    
31.         return L[1:]
    
32. 
    
33. def member(X,L):
    
34. 
    
35.     if L ==[]:
    
36.         return False
    
37. 
    
38.     if X == get_head(L):
    
39. 
    
40.         return True
    
41.     else:
    
42. 
    
43.         return member(X,get_tail(L))
    
44. 
    
45. def length(L):
    
46. 
    
47.     if L == []:
    
48. 
    
49.         return 0
    
50. 
    
51.     else:
    
52.         return 1 + length(get_tail(L))
    
53. 
    
54. def split(L):
    
55. 
    
56.     len = length(L)
    
57. 
    
58.     for i in range(len):
    
59. 
    
60.         start = 100
    
61. 
    
62.         end = 0
    
63. 
    
64.         temp = L[i]
    
65. 
    
66.         for j in range(len):
    
67. 
    
68.             if j < start and L[i] == L[j]:
    
69. 
    
70.                 start = j
    
71. 
    
72.             if member(temp, L[j:]):
    
73. 
    
74.                 if j > end:
    
75. 
    
76.                     end = j
    
77. 
    
78.         memo.append([start,end])
    
79. 
    
80. def print_all():
    
81. 
    
82.     for i in range(length(memo)):
    
83. 
    
84.         small = memo[i][0]
    
85. 
    
86.         big = memo[i][1]
    
87. 
    
88.         for j in range(length(memo)):
    
89. 
    
90.             if not (memo[j][1]< small or memo[j][0] > big):
    
91. 
    
92.                 if memo[j][0] < small:
    
93. 
    
94.                     small =  memo[j][0]
    
95. 
    
96.                 elif memo[j][1] > big:
    
97. 
    
98.                     big = memo[j][1]
    
99. 
    
100.         if [small,big+1] not in memo1:
     
101. 
     
102.             memo1.append([small,big+1])
     
103. 
     
104. 
     
105.     for i in range(length(memo1)):
     
106. 
     
107.         print(S[memo1[i][0]:memo1[i][1]])
     
108. 
     
109. 
     
110. split(lst)
     
111. print_all()

复制代码

output:

1. ababcbaca
   
2. defegde
   
3. hijhklij

复制代码