leetcode763.划分字母区间

leetcode763.划分字母区间

二月 23, 2020

leetcode763. 划分字母区间

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

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

我的思路：

用一个map来记录字母出现的最后一次的位置，记做last。然后遍历这之前的所有字母，检查是否有值比这个last大，比这个大，说明这个字母不能作为分隔点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public List<Integer> partitionLabels(String S) {
      LinkedHashMap<Character,Integer>map=new LinkedHashMap<>();
       for(int i=0;i<S.length();i++){
           	map.put(S.charAt(i), i);
       }
       //如果用linkedHashMap下面这些排序的过程就能省略
		// List<Map.Entry<Character,Integer>>listEntry=new ArrayList<>();
		// listEntry.addAll(map.entrySet());
		// Collections.sort(listEntry, new Comparator<Map.Entry<Character, Integer>>(){
		// @Override
		// public int compare(Map.Entry<Character, Integer> o1, Map.Entry<Character, Integer> o2) {
		// 	// TODO Auto-generated method stub
		// 	return o1.getValue()-o2.getValue();
		// }
		// });
       ArrayList<Integer>result=new ArrayList<>();
       int last=0,flag=0;
       for(Map.Entry<Character,Integer>entry:map.entrySet()) {
       	flag=0;
       	char nowChar=entry.getKey();
       	int now=entry.getValue();
           if(last>now)continue;//linkedHashMap才需要比较
       	for(int i=last;i<now;i++) {
       		if(map.get(S.charAt(i))>now) {
       			flag=1;
       			break;
       		}
       	}
       	if(flag==1)continue;
       	result.add(now-last+1);
       	last=now+1;
       }
       return result;
   }

我自己的写法中在for内部又多了一层for，这样浪费了时间，看看官方解法：

官方解法

维护一个窗口，如果当前字母出现的最后一次的位置（last）比右边界大，那么需要拓展窗口，当 i 与 j 相遇的时候,说明窗口内部所有的字母都符合条件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public List<Integer> partitionLabels(String S) {
        int[] last = new int[26];
        for (int i = 0; i < S.length(); ++i)
            last[S.charAt(i) - 'a'] = i;
        
        int j = 0//右窗口;
        int anchor = 0//左窗口;
        List<Integer> ans = new ArrayList();
        for (int i = 0; i < S.length(); ++i) {
            j = Math.max(j, last[S.charAt(i) - 'a']);
            if (i == j) {
                ans.add(j - anchor + 1);
                anchor = i + 1;
            }
        }
        return ans;
    }

leetcode 21/100