【LeetCode】貪心算法--劃分字母區(qū)間（763）

honhon 發(fā)布于2019-07-31 11:21 / 2963人閱讀

摘要：寫在前面今天這篇文章是貪心算法系列的第三篇劃分字母區(qū)間。前文回顧貪心算法分發(fā)糖果刷題匯總匯總貼今日題目字符串由小寫字母組成。返回一個表示每個字符串片段的長度的列表。示例輸入輸出解釋劃分結果為。每個字母最多出現(xiàn)在一個片段中。

寫在前面

今天這篇文章是貪心算法系列的第三篇--劃分字母區(qū)間。

前文回顧：

【LeetCode】貪心算法--分發(fā)糖果（135）

刷題匯總：

【LeetCode】匯總貼（NO.1-20）

今日題目

字符串 S 由小寫字母組成。我們要把這個字符串劃分為盡可能多的片段，同一個字母只會出現(xiàn)在其中的一個片段。返回一個表示每個字符串片段的長度的列表。

示例 1:
輸入: S = "ababcbacadefegdehijhklij"
輸出: [9,7,8]
解釋:
劃分結果為 "ababcbaca", "defegde", "hijhklij"。
每個字母最多出現(xiàn)在一個片段中。
像 "ababcbacadefegde", "hijhklij" 的劃分是錯誤的，因為劃分的片段數(shù)較少。

注意:
S的長度在[1, 500]之間。
S只包含小寫字母"a"到"z"。

題目分析

解決此題關鍵就是找到能分割的條件，對S的每個字符進行判斷，看是否此字符是被分割到另一個字符中，從題目中得到每個字母最多出現(xiàn)在一個片段中，那么從第一個字符開始，它的最后一個相同的字符一定在這個片段中，得到第一個條件：

當此字符在前面分割中出現(xiàn)，就不能當做分割點

只有這個條件就可以了嗎？我們再考慮一下，當前字符并沒有在前面分割的區(qū)間中出現(xiàn)，是不是能直接作為分割點呢？以下面的字符串為例進行分割。

“aaaaab cdaefgh”
當判斷b的時候，先在前面已經分好的字符串aaaaa里面沒有，符合找到的第一個條件，如果我們把b當做新的分割點，很明顯是錯誤的，因為在b后面的字符串里，又一次出現(xiàn)了a，當我們以b作為分割點是不符合條件的，因此得到第二個限制條件：
分割點后面不能出現(xiàn)前面一個字符串中的字符。

進行了上面的分析但是可以用python做個弊,使用rindex()方法，從第一個字符開始，假設位置為a，用rindex方法找到最后一次出現(xiàn)的位置b，那么這個區(qū)間就為[a,b]。之后每個字符都找最后一個位置，如果在區(qū)間之外則擴大區(qū)間，如果遍歷到區(qū)間的最后一個位置，則結束，長度就為結束位置減開始位置加1。

代碼實現(xiàn)

class Solution:

def partitionLabels(self, S):
    """
    :type S: str
    :rtype: List[int]
    """

    i = 0
    res = []
    while i < len(S):
        start = i
        end = S.rindex(S[i])
        for j in range(i,len(S)):
            last = S.rindex(S[j])
            if last > end:
                end = last
            elif j == end:
                res.append(end-start + 1)
                i = end + 1
                break
    return res