给一个非常长的字符串str 另一个字符集比方{a,b,c} 找出str 里包括{a,b,c}的最短子串。要求O(n).
比方，字符集是a,b,c，字符串是abdcaabcx，则最短子串为abc。
设置Front和Rear，使用对象记录字符集已有值的个数和位置，通过Front和Rear遍历字符串。
遍历过程为Rear在前，当遇到字符集中字符时，该字符个数加1，记录该字符位置。
出现字符集都出现时，计算字串长度；然后，front前移一位，假设此位在字符集中，清空对象记录字符集的状态。
最后获得字串的最小长度和字串位置。
import java.util.HashMap;
import java.util.Map; public class TestMini { /**
* @param args
*/
public static void main(String[] args) {
TestMini min = new TestMini();
min.init();
System.out.println(min.run());
} private String str = "abddddcasdfadfasdfsdfbcx";
private Map<Character, Integer[]> map = new HashMap<Character, Integer[]>(); public void init(){
map.put('a', new Integer[]{0, 0});
map.put('b', new Integer[]{0, 0});
map.put('c', new Integer[]{0, 0});
} public int run(){
char[] chars = str.toCharArray();
Object value = null;
Integer[] il = null;
int front = 0;
int rear = 0;
int minSum = chars.length;
int count = 0;
Object key = null;
for(; rear < chars.length; rear++){
key = chars[rear];
value = map.get(key);
if(value != null){
il = (Integer[])value;
il[1]++;
il[0] = rear;
if(isValid()){
count = getCount();
minSum = (minSum > count)? count : minSum;
checkFront(front);
front++;
}
}
}
return minSum+1;
} private void checkFront(int front){
Object value = map.get(str.charAt(front));
if(value != null){
Integer[] il = (Integer[])value;
il[1]--;
il[0] = 0;
}
} private boolean isValid(){
for(Integer[] entry : map.values()){
if(entry[1] <= 0){
return false;
}
}
return true;
} private int getCount(){
int min = str.length();
int max = 0;
for(Integer[] entry : map.values()){
if(entry[0] < min){
min = entry[0];
}
if(entry[0] > max){
max = entry[0];
}
}
return max - min;
}
}
