求最小子串

给定一个字符串source和一个目标字符串target，在字符串source中找到包括所有目标字符串字母的子串。

注意事项

如果在source中没有这样的子串，返回”“，如果有多个这样的子串，返回起始位置最小的子串。

说明

在答案的子串中的字母在目标字符串中不需要具有相同的顺序

样例

给出source = “ADOBECODEBANC”，target = “ABC” 满足要求的解 “BANC”

代码

import java.util.Scanner;

/**
* @ClassName: LeastSubString
* @Description: 求字符串A中包含B的最小子串--------时间复杂度O(n)
* 如：A{ADOBECODEBANC},B{ABC},则最小子串为BANC
* @author kooking
* @date 2018年9月8日 下午10:03:45
*/ 

//1、先记录下目标字符串B中每个字符的出现的次数
//2、遍历字符串A：
//  2.1、count记录匹配字符的数量，每当匹配一个加一，当count==B的长度时则认为找到最小子串
//          min记录最小子串长度，minString记录最小子串
//          start代表最小子串的起始下标，end代表最小子串的结束下标
//  2.2、找到最小子串后，尝试将最小子串缩小（只能移动start）
//  2.3、继续往后移动：start往后移动一位，并且count减一，继续寻找最小子串
public class LeastSubString {

    public static String getLeastSubString(char[] source,char[] target) {
        if (source==null||target==null) {
            return "";
        }

        int slen=source.length;
        int tlen=target.length;

        //记录source、target每个字符出现的次数
        //source[]记录的是临时最长子串的每个字符出现的次数
        int[] s=new int[256];
        int[] t=new int[256];

        //统计目标串中每个字符出现的次数；
        for (int i = 0; i < tlen; i++) {
            t[target[i]]++;
        }

        int begin=-1,end=slen,count=0,minLen=slen;

        for (int i = 0,start=0; i < slen; i++) {
            s[source[i]]++;
            // 如果加1后这个字符的数量不超过目标串中该字符的数量，则找到了一个匹配字符
            //比较源串中的字符是否在目标串中出现过；
            //这里必须是小于等于，若大于，说明该字符是多出来或者target中未出现的
            if(s[source[i]]<=t[source[i]]){ 
                count++;//更新出现的字符的个数；
            } //为了将目标字符串中出现的字符都包含！

            // 这一点很重要！！！//
            // 如果找到的匹配字符数（只是记录匹配的字符数量）等于目标串长度，说明找到了一个符合要求的子串 
            // 这一点很重要！！！

            if (count == tlen) {
                // 找到最小子串，那么尝试缩小最小子串
                // 将开头没用的都跳过，没用是指该字符出现次数超过了目标串中出现的次数，并把它们出现次数都减1
                while (start < i-tlen && s[source[start]] > t[source[start]]) {
                    s[source[start]]--;
                    start++;
                }

                // 找到符合要求子串的首尾位置start 与 i， 这时候start指向该子串开头的字母，判断该子串长度
                if (i - start < minLen) {
                    minLen = i - start;
                    begin = start;
                    end = i;
                }

                // 缩小最小子串后，found减1，往后寻找更短的满足要求的字符串；
                s[source[start++]]--;
                count--;

            }
        }

        /*如果beg值为-1，说明不存在这样的子串*/  
        if (begin == -1)  
            return "";  
        else  
            return subString(source,begin, end + 1);
    }


    /**
    * @Title: subString
    * @Description: 获取数组ch的子串，子串范围，从from（包括）开始，到to（不包括）结束
    * @param ch 要截取子串的字符串
    * @param from 子串开始下标
    * @param to 子串结束下标-1
    * @return   截取的子串
    * @return String    返回类型
    * @throws
    */ 
    public static String subString(char[] ch,int from,int to) {
        StringBuilder sb=new StringBuilder();
        for (int i = from; i < to; i++) {
            sb.append(ch[i]);
        }
        return sb.toString();
    }


    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        while (scanner.hasNext()) {
            String source = scanner.nextLine();
            if ("exit".equals(source)) {
                break;
            }
            String target = scanner.nextLine();
            String substring=getLeastSubString(source.toCharArray(), target.toCharArray());

            int count=substring.length();
            System.out.println(count+":"+substring);
        }
        scanner.close();
    }
}

测试结果

ADOBECODEBANC
ABC
4:BANC
abchfdhsab
ah
3:hsa
exit

这里就不详细解释算法的步骤了，关键的地方都在代码中注释了

参考:

Lintcode–004（最小子串覆盖）