763. 划分字母区间

Myth丶恋晨 2024-04-01 15:14 66阅读 0赞

### 763. 划分字母区间 ###

#### 题目： ####

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

##### 示例： #####

> 输入：S = “ababcbacadefegdehijhklij”  
> 输出：\[9,7,8\]  
> 解释：  
> 划分结果为 “ababcbaca”, “defegde”, “hijhklij”。  
> 每个字母最多出现在一个片段中。  
> 像 “ababcbacadefegde”, “hijhklij” 的划分是错误的，因为划分的片段数较少。

##### 提示： #####

S的长度在\[1, 500\]之间。  
S只包含小写字母 ‘a’ 到 ‘z’ 。

#### 题解：（贪心） ####

由于同一个字母只能出现在同一个片段，显然同一个字母的第一次出现的下标位置和最后一次出现的下标位置必须出现在同一个片段。因此需要遍历字符串，得到每个字母最后一次出现的下标位置。

在得到每个字母最后一次出现的下标位置之后，可以使用贪心的方法将字符串划分为尽可能多的片段，具体做法如下。

*  从左到右遍历字符串，遍历的同时维护当前片段的开始下标 start 和结束下标 end，初始时 start=end=0。
 *  对于每个访问到的字母 c，得到当前字母的最后一次出现的下标位置 endc，则当前片段的结束下标一定不会小于 endc ，因此end=max⁡(end,endc)。
 *  当访问到下标 end 时，当前片段访问结束，当前片段的下标范围是 \[start,end\]，长度为 end−start+1，将当前片段的长度添加到返回值，然后令 start=end+1，继续寻找下一个片段。
 *  重复上述过程，直到遍历完字符串

#### 代码：（Java） ####

import java.util.ArrayList;
    import java.util.List;
    
    public class div_letter {
        
    
    	public static void main(String[] args) {
        
    		// TODO 自动生成的方法存根
    		String S = "ababcbacadefegdehijhklij";
    		System.out.println(partitionLabels(S));
    	}
    	public static List<Integer> partitionLabels(String s) {
        
    		int last[] = new int[26];
    		int length = s.length();
    		for(int i=0; i<length; i++) {
        
    			last[s.charAt(i) - 'a'] = i;
    		}
    		List<Integer> partition = new ArrayList<Integer>();
    		int start = 0, end = 0;
    		for(int i=0; i<length; i++) {
        
    			end = Math.max(end, last[s.charAt(i) - 'a']);
    			if(i == end) {
        
    				partition.add(end - start + 1);
    				start =  end + 1;
    			}
    		}
    		return partition;
        }
    }

##### 复杂度分析： #####

*  时间复杂度：O(n)，其中n是字符长的长度
 *  空间复杂度：O(∣Σ∣)，其中 Σ是字符串中的字符集

##### 注： 仅供学习参考！ #####

来源：[力扣][Link 1]

[Link 1]: https://leetcode.cn/problems/partition-labels/description/