题目大意：把字符串分割成尽量多的不重叠子串，输出子串的长度数组。要求相同字符只能出现在一个子串中。
Problem:
A string S of lowercase letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.
Example 1:
|
1 2 3 4 5 6 |
Input: S = "ababcbacadefegdehijhklij" Output: [9,7,8] Explanation: The partition is "ababcbaca", "defegde", "hijhklij". This is a partition so that each letter appears in at most one part. A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits S into less parts. |
Solution 0: Brute Force
Time complexity: O(n^2)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
// Author: Huahua // Running time: 15 ms class Solution { public: vector<int> partitionLabels(string S) { vector<int> ans; size_t start = 0; size_t end = 0; for (size_t i = 0; i < S.size(); ++i) { end = max(end, S.find_last_of(S[i])); if (i == end) { ans.push_back(end - start + 1); start = end + 1; } } return ans; } }; |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
""" Author: Huahua Running time : 48 ms """ class Solution: def partitionLabels(self, S): ans = [] start, end = 0, 0 for i in range(len(S)): end = max(end, S.rfind(S[i])) if i == end: ans.append(end - start + 1) start = end + 1 return ans |
Solution 1: Greedy
Time complexity: O(n)
Space complexity: O(26/128)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// Author: Huahua // Running time: 6 ms class Solution { public: vector<int> partitionLabels(string S) { vector<int> last_index(128, 0); for (int i = 0; i < S.size(); ++i) last_index[S[i]] = i; vector<int> ans; int start = 0; int end = 0; for (int i = 0; i < S.size(); ++i) { end = max(end, last_index[S[i]]); if (i == end) { ans.push_back(end - start + 1); start = end + 1; } } return ans; } }; |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// Author: Huahua // Running time: 16 ms class Solution { public List<Integer> partitionLabels(String S) { int lastIndex[] = new int[128]; for (int i = 0; i < S.length(); ++i) lastIndex[(int)S.charAt(i)] = i; List<Integer> ans = new ArrayList<>(); int start = 0; int end = 0; for (int i = 0; i < S.length(); ++i) { end = Math.max(end, lastIndex[(int)S.charAt(i)]); if (i == end) { ans.add(end - start + 1); start = end + 1; } } return ans; } } |
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
""" Author: Huahua Running time: 78 ms """ class Solution: def partitionLabels(self, S): last_index = {} for i, ch in enumerate(S): last_index[ch] = i start = end = 0 ans = [] for i, ch in enumerate(S): end = max(end, last_index[ch]) if i == end: ans.append(end - start + 1) start = end + 1 return ans |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment