関小君刷题记

题目大意：

字符串的排列

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。

换句话说，第一个字符串的排列之一是第二个字符串的子串。

示例1:

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

示例2:

输入: s1= "ab" s2 = "eidboaoo"
输出: False

注意：

1. 输入的字符串只包含小写字母
2. 两个字符串的长度都在 [1, 10,000] 之间

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=567

解题思路分析：

这道题目与我们上一篇文章介绍的 LEETCODE 438. Find All Anagrams in a String 解题思路分析 几乎是如出一辙。本题求的是一个字符串中是否包含与另一个字符串相同的异位词子串，而上一题求的是将所有异位词子串的下标打印出来。相对于上一题目，本题稍微简单一些，但是实现原理没有任何差别，都是要使用到双指针的概念。如果你能完全理解上一篇文章的精髓，再利用本题来练手是个不错的选择。因此本题就不过多的进行思路分析了。直接上代码。

实现代码：

public boolean checkInclusion(String s1, String s2) {
    int[] s1Count = new int[26];
    for(char c : s1.toCharArray()){
        s1Count[c-'a']++;
    }
    int left=0;
    int[] s2Count = new int[26];
    for(int right=0;right<s2.length();right++){
        int current = s2.charAt(right)-'a';
        if(s1Count[current]==0){
            left=right+1;
            s2Count=new int[26];
        }else if(s2Count[current]<s1Count[current]){
            s2Count[current]++;
            if(isSame(s1Count,s2Count)) return true;
        }else if(s2Count[current]==s1Count[current]){
            s2Count[current]++;
            while(left<right){
                int leftChar = s2.charAt(left)-'a';
                s2Count[leftChar]--;
                left++;
                if(leftChar==current){
                    if(isSame(s1Count,s2Count)) return true;
                    break;
                }
            }
        }
    }
    return false;
}

boolean isSame(int[] s1Count, int[] s2Count){
    for(int i=0;i<26;i++){
        if(s1Count[i]!=s2Count[i]) return false;
    }
    return true;
}

本题解法执行时间为4ms。

Runtime: 4 ms, faster than 81.57% of Java online submissions for Permutation in String.

Memory Usage: 39.7 MB, less than 7.69% of Java online submissions for Permutation in String.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-567-permutation-in-string-解题思路分析-2/