763. Partition Labels
LWC 67: 763. Partition Labels
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:
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.
Note:
- S will have length in range [1, 500].
- S will consist of lowercase letters (‘a’ to ‘z’) only.
思路： 很暴力，直接找可以Partition的位置，如果不能Partition，继续向后搜索直到找到第一个可以Partition的位置为止，这样剩余问题就是原问题的子问题了。
初始版本如下：
public List<Integer> partitionLabels(String S) {
List<Integer> ans = new ArrayList<>();
if (S.length() == 0) return ans;
char[] cs = S.toCharArray();
StringBuilder sb = new StringBuilder();
int i = 0;
for (; i < cs.length; ++i) {
sb.append(cs[i]);
if (part(sb, i, S)) {
ans.add(sb.length());
break;
}
}
List<Integer> sub = partitionLabels(S.substring(i + 1));
for (int hello : sub) ans.add(hello);
return ans;
}
public boolean part(StringBuilder sb, int i, String S) {
if (sb.toString().isEmpty()) return false;
for (int j = i + 1; j < S.length(); ++j) {
String letter = S.substring(j, j + 1);
if (sb.toString().contains(letter)) return false;
}
return true;
}再精简一点，因为调用原函数，可以在for循环中完成，所以有：
public List<Integer> partitionLabels(String S) {
List<Integer> ans = new ArrayList<>();
char[] cs = S.toCharArray();
StringBuilder sb = new StringBuilder();
for (int i = 0; i < cs.length; ++i) {
sb.append(cs[i]);
if (part(sb, i, S)) {
ans.add(sb.length());
sb = new StringBuilder();
}
}
return ans;
}
public boolean part(StringBuilder sb, int i, String S) {
if (sb.toString().isEmpty()) return false;
for (int j = i + 1; j < S.length(); ++j) {
String letter = S.substring(j, j + 1);
if (sb.toString().contains(letter)) return false;
}
return true;
}万幸此答案没有超时，实际上我们还可以采用贪心的做法，降低时间复杂度。上个版本中，还需要计算StringBuilder的字符串中的每个字符是否在后续字符中出现过，实际上没有必要，我们只要记录StringBuilder中的每个字符出现的最后一个位置在哪，这样就避免每次都判断一遍，而是利用字符的最后位置直接判断。其次很重要的一点，字符串的partition的依据是：字符串中每个字符最后出现位置的整体最大值。
Java版本：
public List<Integer> partitionLabels(String S) {
List<Integer> ans = new ArrayList<>();
char[] cs = S.toCharArray();
int n = cs.length;
int[] last = new int[32];
for (int i = 0; i < n; ++i) {
last[cs[i] - 'a'] = i;
}
int pre = -1;
int max = 0;
for (int i = 0; i < n; ++i) {
if (last[cs[i] - 'a'] > max) max = last[cs[i] - 'a'];
if (max == i) {
ans.add(max - pre);
pre = max;
max = max + 1;
}
}
return ans;
}Python版本：
class Solution(object):
def partitionLabels(self, S):
"""
:type S: str
:rtype: List[int]
"""
lst = {}
n = len(S)
for i, c in enumerate(S):
lst[c] = i
ans = []
max = 0
pre = -1
for i in range(n):
if lst[S[i]] > max: max = lst[S[i]]
if max == i:
ans.append(max - pre)
pre = max
max = max + 1
return ans