LeetCode 763. Partition Labels（划分字母区间）

题目

解析

分析：题目的要求是把原字符串划分为若干子串，原字符串中出现的字符只会出现在其中一个子串中，子串尽可能划分地多。
思路1：这是我最初的一个想法，写一个内部类Range，它有start和end两个属性，遍历一边字符串，把每个英文字符及其Range保存在HashMap中；然后写一个数组保存断点信息，对每个可断的点进行判断，如果它在某个Range范围内，那么它是不能作为断点的，因为它会导致一个字符在两个字符串中出现；找断点的同时就可以直接得到各个子串的长度了。
解法1：

class Solution {	
    class Range{
    	public int start;
    	public int end;
		public Range(int start, int end) {
			this.start = start;
			this.end = end;
		}    	
    }	
    public List<Integer> partitionLabels(String S) {
    	  HashMap<String, Range> map=new HashMap<>();
          for(int i=0;i<S.length();i++){
        	  String x=S.charAt(i)+"";
        	  if(map.get(x)==null){
        		  map.put(x,new Range(i,i+1));
        	  }else if(map.get(x)!=null){
        		  map.get(x).end=i+1;
        	  }
          }
          int[] cut=new int[S.length()+1];         
          boolean cutFlag=true;
          ArrayList<Integer> arrayList=new ArrayList<>();
          int lastCut=0;
          for(int i=1;i<cut.length;i++){
        	  Iterator<String> iterator=map.keySet().iterator();
        	  while(iterator.hasNext()){
        	      Range range=map.get(iterator.next());
         	  	  if(i>range.start&&i<range.end){
         	  		  cutFlag=false;
         	  	  }
              }
        	  if(cutFlag==true){
        		  arrayList.add(i-lastCut);
        		  lastCut=i;
        	  }else{
        		  cutFlag=true;
        	  }
          } 
          return arrayList;         
    }
}

思路2：上面的那种方法耗时比较长，且一些细节的处理会有些困难，我决定换一种思路来实现。之前保存的是字符出现的范围，现在换为统计它最后一次出现的位置，为什么可以不保存字符出现的第一个位置呢？因为第一个字符可以通过遍历一遍字符串得到位置。这种思想在解题中使用很多，涉及到两个信息的问题可以拆解为用一个数据结构保存一种信息，然后一次遍历得出结果。先遍历一次字符串，保存每个字符最后一次出现的位置在数组中，然后从字符串的第一个位置开始第二轮遍历，先以第一个字符的的位置到它最后一次出现的位置为范围开始循环判断在这个范围中的每个字符的最后一次出现位置是否在它的范围内，如果在范围外，则调整范围，当循环结束后，范围内的字符必然只出现在这个范围内，它就是一个子串，此时可以保存该子串的长度，然后从下一个位置开始新一轮查找，原理同上，直到范围的末尾被调整到最后一个位置。
解法2（19ms）：

public class Solution2 {	
	public List<Integer> partitionLabels(String S){	
	      ArrayList<Integer> arrayList=new ArrayList<>();	      
	      int[] last=new int[26];	      
	      for(int i=0;i<S.length();i++){
	    	    char x=S.charAt(i);
	    	    if(i>last[x-'a'])
	    	    last[x-'a']=i;
	      }
	      int i=0;
	      int index=0;
	      while(i<S.length()){
	    	  index=last[S.charAt(i)-'a'];
	    	  for(int k=0;k<index;k++){
	    		  if(last[S.charAt(k)-'a']>index){
	    			  index=last[S.charAt(k)-'a'];
	    		  }
	    	  }
	    	  arrayList.add(index-i+1);
	    	  i=index+1;
	      }
		  return arrayList;		  		
	}						
}