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