每日力扣：567. 字符串的排列

港控/mmm° 2022-03-02 11:22 223阅读 0赞

package com.sample.suncht.algo;
    
    import java.util.ArrayList;
    import java.util.List;
    
    /**
     * 567. 字符串的排列
     *
     * 给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
     *
     * 换句话说，第一个字符串的排列之一是第二个字符串的子串。
     *
     * 示例1:
     *
     * 输入: s1 = "ab" s2 = "eidbaooo"
     * 输出: True
     * 解释: s2 包含 s1 的排列之一 ("ba").
     *
     *
     * 示例2:
     *
     * 输入: s1= "ab" s2 = "eidboaoo"
     * 输出: False
     *
     *
     * 注意：
     *
     * 输入的字符串只包含小写字母
     * 两个字符串的长度都在 [1, 10,000] 之间
     *
     *
     * 时间复杂度：O(m), 空间复杂度：O(n)
     * 执行耗时：17 ms
     */
    public class CheckInclusion567 {
        public boolean checkInclusion(String s1, String s2) {
            if(s1.length() > s2.length()) {
                return false;
            }
    
            //将字母分布的到26个桶内
            int[] bucket = new int[26];
            char[] chars1 = s1.toCharArray();
            for (int i = 0; i < chars1.length; i++) {
                bucket[chars1[i] - 'a'] += 1;
            }
    
            // 统计s1的字母个数
            int sum = chars1.length;
    
    
            char[] chars2 = s2.toCharArray();
            for (int i = 0; i < chars2.length; i++) {
                //使用滑动窗口，长度为s1.length
                //1. 前s1.length长度中，s2的每个字母是否在桶中出现，sum就减1，如果sum==0，则说明存在该排列
                //2. 大于s1.length长度部分，随着滑动窗口移动一个字母，需要将窗口前面的一个字母重新补回来，即在桶中出现过，则sum++， 同时将窗口新加入的
                //   字母，判断是否在桶中出现。如果窗口内sum==0，则说明存在该排列
                if(i >= chars1.length) {
                    if(bucket[chars2[i - chars1.length] - 'a'] >= 0) {
                        sum++;
                    }
                    bucket[chars2[i - chars1.length] - 'a'] += 1;
                }
    
                if(bucket[chars2[i] - 'a'] > 0) {
                    sum--;
                }
    
                bucket[chars2[i] - 'a'] -= 1;
    
                if(sum == 0) {
                    return true;
                }
            }
    
            return false;
        }
    
        public static void main(String[] args) {
            List<AlgoHelper.BiInputParams<String, String, Boolean>> datas = new ArrayList<>();
            datas.add(new AlgoHelper.BiInputParams<>("ab", "eidbaooo", true));
            datas.add(new AlgoHelper.BiInputParams<>("ab", "eidboaoo", false));
            datas.add(new AlgoHelper.BiInputParams<>("dsc", "eidcqsoo", true));
            datas.add(new AlgoHelper.BiInputParams<>("a", "a", true));
            AlgoHelper.assertResult(datas, new CheckInclusion567()::checkInclusion);
        }
    
    
    }