LEETCODE 567. Permutation in String 解题思路分析

题目大意:

字符串的排列

给定两个字符串 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

解题思路分析:

如果s1的任意一种排列是s2的一个子串,那么说明s1中每种字母的个数要与s2某个子串所有字母个数完全相同,因此,本题首先要统计出s1中所包含的每种字母数量,将其保存在数组count中。然后使用双指针方式来遍历s2,起始时,左右两指针均在第0位。利用右指针不断加一来查看当前字符,在count数组中,当前字符的数量减一。减一操作后,如果count的值为0,说明当前字符消耗掉了所有s1中的当前字符,这时查看一下左右区间的长度,如果该长度等于s1的长度,那么说明当前区间可以匹配上s1,直接返回true。如果count值为-1,说明当前字符不存在于s1中,或者当前区间内的当前字符数量多于s1中的数量,此时向右逐步移动左指针,左指针经过的位置表示已经移出区间,此时在count数组中要对相应的字符个数加一,直到出现左指针与右指针指向了相同的字符为止,右指针所指的字符个数count由-1变为0,接下来继续移动右指针,重复上述操作。

实现代码:

public boolean checkInclusion(String s1, String s2) {
    // 统计s1中所有字母数量
    int[] count = new int[26];
    for(int i=0;i<s1.length();i++){
        count[s1.charAt(i)-'a']++;
    }
    // 定义左右指针
    int left=0, right=0;
    while(left<s2.length()&&right<s2.length()){
        // 当前字符
        int c = s2.charAt(right)-'a';
        // 当前字符数量减一
        count[c]--;
        // 如果当前数量为0
        if(count[c] == 0){
            // 区间长度正好等于s1长度时,说明完全匹配,返回true
            if(right-left+1==s1.length()) return true;
        }else if(count[c]<0){ // 如果当前数量小于0
            // 移动左指针
            while(left<=right){
                // 左指针字符
                int leftChar = s2.charAt(left++)-'a';
                // 左指针字符数量加一
                count[leftChar]++;
                // 左右指针字符相同时,结束移动左指针
                if(leftChar==c){
                    break;
                }                    
            }
        }
        right++; // 右指针加一
    }
    return false;
}

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

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

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

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-567-permutation-in-string-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。