关于SubString的解决方案

发表于 | 分类于

前言

对于大多数关于子字符串的问题，我们要解决的问题很多都可以概括为给定一个字符串，要求我们在这个给定的字符串中找到满足某些条件的子字符串。

对于上述的问题，在此我们提供一种求解的思路：利用HashMap来统计每种字符的个数加上由2个整形指针构成的滑动窗口来解决。说到这，可能还是不知道说的啥。别急，我们先解决一个简单的问题:LeetCode第3题 Longest Substring Without Repeating Characters

小试牛刀

问题描述：给定一个字符串，找到最长的满足条件的子字符串，要求子字符串没有重复的字符。

话不多说，先上代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int lengthOfLongestSubstring(String s) {
    if (s == null || s.length() == 0) {
        return 0;
    }
    int[] hash = new int[256];
    int l = 0, r = 0;
    int d = Integer.MIN_VALUE;
    while (r < s.length()) {
        hash[s.charAt(r)]++;
          d = d > r - l ? d : r - l;
        while (hash[s.charAt(r)] >= 2) {
            hash[s.charAt(l)]--;
            l++;
        }
        r++;
    }
    d = d > r - l ? d : r - l;
    return d;
}

思路：

首先，我们定义了一个数组 int[] hash = new int[256]; 数组的下标范围是［0-255］,char类型中所有英文字符的ACSII码的范围在0-255之间，所以我们可以使用这个数组来统计各种字符出现的个数。这里整数数组的功能就相当于一个HashMap，但是比HashMap高效一点。

然后，我们定义了2个指针，由这2个指针在原字符串中确定了一个滑动的窗口，我们每次判断滑动窗口中的子字符串是否满足条件，如果满足就统计其长度，如果不满足就滑动指针，继续搜索。

我们来模拟一下上述算法的工作：

滑动窗口初始大小为0，指向原字符串的首位，然后我们逐步增大滑动窗口，移动r指针，然后统计滑动窗口中每种字符出现的个数。如果滑动窗口中的字符构成的子字符串满足条件（每种字符的出现个数不大于1）那么，就统计其长度，并记录最长的长度，继续滑动r指针，扩大窗口大小。如果出现滑动窗口中的子字符串不满足条件的情况，那么就缩小滑动窗口的大小，移动l指针，直到滑动窗口中的子字符串满足条件为止.依次反复，直到滑动窗口达到原字符串的边界,返回最长的长度即可。

从这题，我们就可以看到一点门道了：滑动窗口就是我们搜索解的工具，或者是搜索的方法，而hash数组就是来统计滑动窗口中的每种字符出现的个数，来判断是否满足指定的限制。每次移动r指针，是扩大滑动窗口大小，如果出现滑动窗口不满足限制条件，就移动l指针，缩小窗口大小，使之满足条件。

学以致用

有了上述题的启发，再来看一道题，试试手：LeetCode第76题 Minimum Window Substring

问题描述：给定2个字符串S，T，要求在字符串S中找到最小的满足条件的子字符串，要求该子字符串中包含了字符串T中所有字符。例如，S＝“ADOBECODEBANC”，T＝“ABC”，那么最小的窗口为“BANC”。

按照上述提供的思路，同样给出基于滑动窗口和HashMap的解法：

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
35
36
37
public String minWindow(String s, String t) {
       if (s == null || s.length() == 0 || t == null || t.length() == 0) {
           return "";
       }
       int[] hash = new int[256];
       for (char c : t.toCharArray()) {
           hash[c]++;
       }
       int l = 0, r = 0;
       int minWindowHead = 0;
       int count = t.length();
       int d = Integer.MAX_VALUE;
       while (r < s.length()) {
           if (hash[s.charAt(r)] >= 1) {
               count--;
           }
           hash[s.charAt(r)]--;
           r++;
           while (count == 0) {
               if (hash[s.charAt(l)] == 0) {
                   count++;
               }
               if (r - l < d) {
                   d = r - l;
                   minWindowHead = l;
               }
               hash[s.charAt(l)]++;
               l++;
           }
       }
       return d == Integer.MAX_VALUE ? "" : s.substring(minWindowHead, d + minWindowHead);
   }

我们可以看到算法的核心还是利用hash数组(充当HahsMap的功能)加上滑动窗口来搜索满足条件的解，并在搜索的过程中记录下最小的窗口。

思路：由于要找到一个最小的窗口，使之包含字符串T中所有的字符，那么我们先统计字符串T中的所有字符，来初始化hash数组。然后，同样的方法逐步扩大滑动窗口的大小，直到找到满足条件的窗口。这里，我们利用了一个int类型的变量count(初始值为字符串T的长度)来判断滑动窗口是否包含了T中所有的字符，count每次遇到字符串T中包含的字符就减1，如果count＝＝0，那么说明该窗口已经包含了字符串T中所有的字符，可以记录其长度了，同时还可以逐步缩小滑动窗口的大小来寻找较小的滑动窗口，在缩小窗口大小的时候也要保证滑动窗口满足条件，在缩小窗口的时候也需要维护hash数组，以及count变量的值。如果不满足条件，就退出循环，继续扩大窗口大小。

现在已经有了2道题的经验了，稍微做一点总结。以上2道题的类型都差不多，给定一个字符串要求找到满足条件的子字符串，并且在这些满足限制的子字符串中找到最小或者最大的那个。我们的思路是利用滑动窗口找到所有满足条件的子字符串，滑动窗口的控制由2个指针来操作，r指针用来扩大窗口，l指针用来缩小窗口。在滑动窗口滑动的过程中，利用HashMap(hash数组)来统计窗口中每种字符的个数，然后根据不同的限制条件来判断即可。

闻鸡起舞

同样，类似的题目还有很多。例如LeetCode第438题 Find All Anagrams in a String和LeetCode第159题 Longest Substring with At Most Two Distinct Characters。这2道题也是同样的思路，类似的解法。

159题 Longest Substring with At Most Two Distinct Characters:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int lengthOfLongestSubstringTwoDistinct(String s) {
    Map<Character,Integer> map = new HashMap<>();
    int start = 0, end = 0, counter = 0, len = 0;
    while(end < s.length()){
        char c = s.charAt(end);
        map.put(c, map.getOrDefault(c, 0) + 1);
        if(map.get(c) == 1) counter++;
        end++;
        while(counter > 2){
            char cTemp = s.charAt(start);
            map.put(cTemp, map.get(cTemp) - 1);
            if(map.get(cTemp) == 0){
                counter--;
            }
            start++;
        }
        len = Math.max(len, end-start);
    }
    return len;
}

解析：要求找到最长的最多包含2种字符的子字符串，利用滑动窗口加上HashMap很好解决这个问题，counter变量表示当前滑动窗口中有多少种字符，如果大于2，说明滑动窗口不满足条件，就要缩小滑动窗口直到其满足条件。

438题 Find All Anagrams in a String:

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
35
public List<Integer> findAnagrams(String s, String p) {
       List<Integer> result = new ArrayList<Integer>();
       if (s == null || s.length() == 0 || p == null || p.length() == 0) {
           return result;
       }
       int[] hash = new int[256];
       int l = 0, r = 0;
       int count = p.length();
       for (char c : p.toCharArray()) {
           hash[c]++;
       }
       while (r < s.length()) {
           if (hash[s.charAt(r)] >= 1) {
               count--;
           }
           hash[s.charAt(r)]--;
           r++;
           if (count == 0) {
               result.add(l);
           }
           if (r - l == p.length()) {
               if (hash[s.charAt(l)] >= 0) {
                   count++;
               }
               hash[s.charAt(l)]++;
               l++;
           }
       }
       return result;
   }

解析：题目希望找到所有满足条件的子字符串，要求子字符串是给定字符串的anagram(由颠倒字母顺序而构成的字)。同样的思路，我们在操作滑动窗口的时候，count==0表示找到了一个符合条件的子字符串，如果count!=0且这时滑动窗口的大小等于要求的子字符串的长度，说明该子字符串不可能是anagram，那么就缩小滑动窗口(每次缩小1位,l指针加1)。这么做的目的是时刻保持滑动窗口是小于等于给定子字符串的长度的，保证在搜索的过程中不遗漏可能的解。按照上述代码中的写法，其实我们是搜索(滑动窗口遍历)了以原字符串中所有字符为起点且长度为要求子字符串长度的子字符串，在这些可能的解中判断是否有满足要求的解，这样就保证了不会遗漏。

模版

针对我们这种方法，甚至有人还总结出了解题的模版，告诉我们如何利用滑动窗口和HashMap来解决类似的子字符串问题。

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
int findSubstring(string s){
        vector<int> map(128,0);
        int counter; // check whether the substring is valid
        int begin=0, end=0; //two pointers, one point to tail and one  head
        int d; //the length of substring
        for() { /* initialize the hash map here */ }
        while(end<s.size()){
            if(map[s[end++]]-- ?){  /* modify counter here */ }
            while(/* counter condition */){ 
                 
                 /* update d here if finding minimum*/
                //increase begin to make it invalid/valid again
                
                if(map[s[begin++]]++ ?){ /*modify counter here*/ }
            }  
            /* update d here if finding maximum*/
        }
        return d;
  }

上述模版是我搬运过来的，我个人觉得这种模版在解题的过程中也没多大用处，只要把握住核心的思路，在解题的时候自然而然就能写出bug free的代码，但是总结出来的模版确实可以帮助我们进一步理解算法。

总结

到此，我们已经学会了一种解决子字符串问题的思路，但是我们解决的问题是有局限的，我发现这种方法只能解决那种对于子字符串的字符顺序没有要求的问题，例如找到最长的子字符串要求没有重复字符等等。如果遇到类似找回文子串的问题(对于子字符串的字符顺序有要求)就无能为力了，找最长回文子串还是老老实实用动态规划求解吧。

这篇博客讨论的问题是我刷题的时候在一个讨论区里面发现的，然后自己做了总结，并且以上题目我自己都AC了，于是写篇博客来总结一下，博客的小标题是我突发奇想来的，纯属自娱自乐。

0%