• 注册
    • 今日签到
    • 连续签到

    暂没有数据

    暂没有数据

    • 查看作者
    • 领扣:1045. Partition Labels

      1045. Partition Labels

      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

      Example 1:
      	Input:  S = "ababcbacadefegdehijhklij"
      	Output:  [9,7,8]
      	
      	Explanation:
      	The partitions are "ababcbaca", "defegde", "hijhklij".
      	A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits S into less parts.
      	
      Example 2:
      	Input: S = "abcab"
      	Output:  [5]
      	
      	Explanation:
      	We can not split it. 
      	

      Notice

      1.S will have length in range [1, 500].
      2.S will consist of lowercase letters ('a' to 'z') only.

      class Solution:
          """
          @param S: a string
          @return: a list of integers representing the size of these parts
          """
          def partitionLabels(self, S):
              # Write your code here
              last = {}
              for each in range(len(S)):
                  last[S[each]] = each
                  
              start, end , i = 0,0,0
              res = []
              while i < len(S) and start < len(S):
              
                  i = start
                  end = last[S[start]]
                  while i < end:
                      
                      end = max(end, last[S[i]])
                      i +=1 
                  res.append(end-start +1)
                  start = end +1 
              return res

       Find the latest position that letter appears in the string, save it to the dictionary.

      Go from the start point to the (max) lastest position it appears in the string.

      until the interval, and save the length, and iterate to the next interval.

      Until the start < length of the string, and return all the saved length of the partition.

      We have to go over the string twice, the time complexity is O(2n) = O(n)

      The most possible dictionary can go is 26, which constant. Space complexity is O(1)

      纽约州·纽约
    • 0
    • 0
    • 0
    • 187