Leetcode 76 Minimum Window Substring(最小窗口的子串），leetcodesubstring

Leetcode 76 Minimum Window Substring(最小窗口的子串），leetcodesubstring

一，问题描述：

1，给定一个字符串S和一个字符串T，在S中找到最短的窗口，该窗口包括字符串T中所有的字符，该时间复杂度为O（n）。
2，举个例如：
S=”ADOBECODEBANC”
T=”ABC”
输出： BANC。

s=”ABCDEFEFEFDCA”
t=”ACD”
输出： DCA

3，解题思路：
总体思想就是先扫描一遍找到最后一个元素满足t字符串的，然后从左边向右开始收缩，使得满足t字符串的最少字符串返回。
这题先用Map统计t中每个字符和每个字符出现的次数，key表示字符，value表示字符出现的次数。设置一个变量count,然后去从左到右扫描s字符串，如果s中的字符与Map中的字符相等的话，则Map中的字符的次数减去1，并且
count加1，如果count值等于t字符串的长度，然后用end-begin+1的长度与给定的lenth相比较，如果end-begin+1小于lenth，则len=end-begin+1，minbegin=begin。然后再用s字符串中第begin的元素去比较map。如果相等的话，Map中的该元素的次数加1，并且count减去1。最后判断lenth的长度，如果大于t字符串的长度，返回空字符，如果小于的话，则返回s.substring
(minbegin,minbegin+len);

二，AC了的程序（用Java实现的）

import java.util.*;
public class Test2{
    public String minWindow(String s,String t)
    {
       if((s==null||s.length()==0)||(t==null||t.length()==0))
        {
            return "";
        }

        if(s.length()<t.length())
        {
            return "";
        }

        int len1=s.length();    //字符串s的长度
        int len2=t.length();   //字符串t的长度

        Map<Character,Integer>map=new HashMap<Character, Integer>(); //这里用map来装字符串t的，其中key表示每个字符，value表示该字符出现的个数
        for(int i=0;i<len2;i++)
        {
            if (map.containsKey(t.charAt(i))) //如果出现相同的字符，则累加在一起的，因为在Map中，不允许key值是相同的。
            {
                map.put(t.charAt(i),map.get(t.charAt(i))+1);
            }
            else
            {
                map.put(t.charAt(i),1);
            }
        }

        int begin=0;
        int num=0;
        int tempnum=Integer.MAX_VALUE;  //初始化一个最大程度为整数最大数
        int minbegin=0;

        for(int end=0;end<len1;end++)  //开始从左到右扫描字符串s
        {
            if(map.containsKey(s.charAt(end)))
            {
                map.put(s.charAt(end),map.get(s.charAt(end))-1);
                if(map.get(s.charAt(end))>=0)
                {
                    num++;
                }
            }

            while(num==len2)
            {
                if(end-begin+1<tempnum)
                {
                    tempnum=end-begin+1; //满足包含字符串t的最小字符串的长度
                    minbegin=begin;   //设置开始的字符
                }

                if(map.containsKey(s.charAt(begin)))
                {
                    map.put(s.charAt(begin),map.get(s.charAt(begin))+1);
                    if(map.get(s.charAt(begin))>0)
                    {
                        num--;  //这样就直接跳出while循环
                    }
                }

                begin++;
            }
        }

        if(tempnum>len1)
        {
            return "";
        }
        String str=s.substring(minbegin,minbegin+tempnum);

        return str;

    }

    public static void main(String []args)
    {
        Test2 test=new Test2();
        Scanner scan=new Scanner(System.in);
        String s=scan.nextLine();
        String t=scan.nextLine();

        String min=test.minWindow(s,t);
        System.out.println("最小字符串: "+min);
    }
}

运行结果：