0763. Partition Labels

763. 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 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.

题目大意 #

这道题考察的是滑动窗口的问题。

给出一个字符串,要求输出满足条件窗口的长度,条件是在这个窗口内,字母中出现在这一个窗口内,不出现在其他窗口内。

解题思路 #

这一题有 2 种思路,第一种思路是先记录下每个字母的出现次数,然后对滑动窗口中的每个字母判断次数是否用尽为 0,如果这个窗口内的所有字母次数都为 0,这个窗口就是符合条件的窗口。时间复杂度为 O(n^2)

另外一种思路是记录下每个字符最后一次出现的下标,这样就不用记录次数。在每个滑动窗口中,依次判断每个字母最后一次出现的位置,如果在一个下标内,所有字母的最后一次出现的位置都包含进来了,那么这个下标就是这个满足条件的窗口大小。时间复杂度为 O(n^2)

代码 #


package leetcode

// 解法一
func partitionLabels(S string) []int {
	var lastIndexOf [26]int
	for i, v := range S {
		lastIndexOf[v-'a'] = i
	}

	var arr []int
	for start, end := 0, 0; start < len(S); start = end + 1 {
		end = lastIndexOf[S[start]-'a']
		for i := start; i < end; i++ {
			if end < lastIndexOf[S[i]-'a'] {
				end = lastIndexOf[S[i]-'a']
			}
		}
		arr = append(arr, end-start+1)
	}
	return arr
}

// 解法二
func partitionLabels1(S string) []int {
	visit, counter, res, sum, lastLength := make([]int, 26), map[byte]int{}, []int{}, 0, 0
	for i := 0; i < len(S); i++ {
		counter[S[i]]++
	}

	for i := 0; i < len(S); i++ {
		counter[S[i]]--
		visit[S[i]-'a'] = 1
		sum = 0
		for j := 0; j < 26; j++ {
			if visit[j] == 1 {
				sum += counter[byte('a'+j)]
			}
		}
		if sum == 0 {
			res = append(res, i+1-lastLength)
			lastLength += i + 1 - lastLength
		}
	}
	return res
}


⬅️上一页

下一页➡️

Calendar Sep 6, 2020
Edit Edit this page
本站总访问量:  次 您是本站第  位访问者