567. 字符串的排列

问题

给定两个字符串 \(s1 \)和 \(s2\),写一个函数来判断 \(s2\) 是否包含 \(s1\) 的排列。
换句话说,第一个字符串的排列之一是第二个字符串的子串。

示例1:

输入: \(s1 = "ab" s2 = "eidbaooo"\)
输出: \(True\)
解释: \(s2\) 包含 \(s1\) 的排列之一 \(("ba")\).

示例2:

输入: \(s1= "ab" s2 = "eidboaoo"\)
输出: \(False\)

注意:

  • 输入的字符串只包含小写字母
  • 两个字符串的长度都在 [1, 10,000] 之间
    ## 解法
    题目乍一看似乎没什么好办法,暴力遍历总是行得通。但是时间复杂度嘛,嘿嘿。

接下来深挖一下题目,既然是判断\(s2\)是否包含\(s1\),那么我们总是可以排除一些明显不满足条件的地方:

  • \(s1\)或\(s2\)为空
  • \(s2\)的长度小于\(s1\)

接下来,我们假设\(s2\)中有\(s1\)的排列\(a\),那么这个排列\(a\)的长度肯定是\(s1\)的长度\(length\),实际上就是判断这两个字符串不管字母顺序是否相同,
判断两个字符串是否相同可以用一个长度为26的数组,遍历第一个,将字母出现的次数记下来,然后遍历另一个字符串将数组中字母出现的次数减小一,当次数减小到-1时,代表不相同,直接返回false。当遍历完仍然没有返回时,那么两个字符串肯定是相同的。
我们可以设置两个指针,一个起始指针\(start\),一个结束指针\(end\),并且有\(end = start +length - 1\)。此时,从\(end\)指针处往回判断。至于为什么从\(end\)处往回走而不是从\(start\)处往前走是因为,我们注意到这样一种情况,当\(end\)处的字符在数组中出现次数已经减到0时,\(end\)处的字符必然不在排列\(a\)中,此时,\(start\)可以直接跳到\(end+1\)处,可以直接过滤掉部分字符。这样也就不用遍历必然失败的场景了。

代码

java实现

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        //  特殊情况直接跳出
        if (s1 == null || s2 == null || s2.length() < s1.length()) {
            return false;
        }
        // 初始化一个数组,将s1的字母出现次数保存在这个数组中去。
        int[] map = new int[26];
        int length = s1.length();
        //遍历s1放入map
        for (int i = 0; i < length; i++) {
            map[s1.charAt(i) - 'a']++;
        }
        //遍历s2,此时注意到这样一个情况,如果s2包含s1,那么s2子串的长度必然等于s1,因此,可以设置两个指针。
        int start = 0, end = length - 1;
        while (end < s2.length()) {
            // 这里是一个注意点,需要注意不能直接用map处理,否则会导致第一次false后,后面的判断全是false
            int[] temp = map.clone();
            while (end >= start) {
                if (temp[s2.charAt(end) - 'a']-- == 0) {
                    break;
                }
                end--;
            }
            //上一层有两种跳出方式,一种break;一种是正确判断完了。需要区分一下。
            if (end < start) {
                //这种是正常判断完成了。直接返回true 
                return true;
            } else {
                //此时注意到这样一种情况,end处必然不能在s2子串中出现。那么start = end+1,end = start+length-1 可以跳过start与end之间的字符,因为这部分字符必然不满足条件。
                start = end + 1;
                end = start + length - 1;
            }
        }
        return false;
    }
}