使用布隆过滤器的思想优化leetcode上567. 字符串的排列

96 阅读 0 评论 64 点赞

我是靠谱客的博主帅气大树，最近开发中收集的这篇文章主要介绍使用布隆过滤器的思想优化leetcode上567. 字符串的排列，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

布隆过滤器介绍

布隆过滤器本身是基于位图的，是对位图的一种改进。位图本质上是一种特殊的哈希表，可以把数据按位映射到一个数字中，来减小空间消耗，但是当数据范围太大，数据量太小，也就是说装填因子太小，空间消耗反而可能会变大，布隆过滤器是为了解决这个问题

使用 K 个哈希函数，对同一个数据求哈希值，那会得到 K 个不同的哈希值，把这 K 个数字作为位图中的下标，也就是说，用 K 个二进制位，来表示一个数据的存在。但是又带来了新的问题，那就是容易误判。

布隆过滤器的误判的特点：如果经过布隆过滤器判断不存在，那说明真的不存在，不会发生误判；如果布隆过滤器判断存在，这个时候才会有可能误判，有可能并不存在。

题目描述

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。

换句话说，s1 的排列之一是 s2 的子串。

提示：

1 <= s1.length, s2.length <= 10^4
s1 和 s2 仅包含小写字母

解题思路

暴力法

首先思考暴力法，在s2中找到与s1字符串大小相同的区间，看这个区间内元素是否属于s1的全排列的一种情况，遍历所有可能的区间需要O(N)时间复杂度，判断是否属于s1的全排列的一种情况本身逻辑就很复杂，时间复杂度O(N)以上，取决于实现思路，所以总的时间复杂度是O(N^)以上

滑动窗口 + 哈希表优化

事实上，这道题目关心的是实际字符的个数而不是字符序列，题目中的说全排列其实是在误导。可以使用哈希表统计s1的各字符个数，在s2中遍历所有与s1长度相同的区间并统计字符哈希表，然后比较两个哈希表是否相同即可。因为只有小写字母，这里使用长度26的数组做映射构造哈希表，来优化空间复杂度

int[] map1 = new int[26], map2 = new int[26];
// 初始化两个数组哈希
initMap(map1, chs1, len1); initMap(map2, chs2, len1);

void initMap(int[] map, char[] chs, int len) {
    for (int i = 0; i < len; i ++) {
        map[chs[i] - 'a'] ++;
    }
}

布隆过滤器优化

经过哈希表优化时间复杂度已经降低到O(26N)。因为每次窗口移动都需要判断两个数组是否相同，实际数组仅发生微小变化，包含大量重复计算。

可以把26个小写字母当成26进制计算s1的26进制结果，将a-z映射到0-26就相当于哈希函数的作用，然后把所有字符映射结果相加，这一步就相当于是构造布隆过滤器。

利用布隆过滤器的误判的特点，如果布隆过滤器判断不存在，那说明真的不存在，不会发生误判；如果某个数字经过布隆过滤器判断存在，这个时候才会有可能误判，有可能并不存在，所以这个时候需要比较哈希表是否一致即可

布隆过滤器的判断仅需O(N)的时间复杂度，而且只要哈希函数设计的好，理论上布隆过滤器发生误判的概率非常小。

时间复杂度可以认为是降低到了O(n)

代码

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int[] map1 = new int[26], map2 = new int[26];
        char[] chs1 = s1.toCharArray(), chs2 = s2.toCharArray();
        int len1 = s1.length(), len2 = s2.length();
        if (len1 > len2) return false;

        // 初始化两个数组哈希
        initMap(map1, chs1, len1); initMap(map2, chs2, len1);
        
        // 计算s1的布隆过滤器值
        int bloomFilter = 0;
        for (int i = 0; i < len1; i ++) {
            bloomFilter += (chs1[i] - 'a');
        }
        int bloomCur = 0;
        for (int i = 0; i < len1; i ++) {
            bloomCur += (chs2[i] - 'a');
        }
        if (bloomFilter == bloomCur && check(map1, map2)) return true;
        
        // 在滑动窗口中先判断布隆过滤器值的值，在判断数组哈希是否一致
        for (int i = len1; i < len2; i ++) {
            bloomCur = bloomCur + (chs2[i] - 'a') - (chs2[i - len1] - 'a');
            map2[chs2[i] - 'a'] ++; map2[chs2[i - len1] - 'a'] --;
            if (bloomFilter == bloomCur && check(map1, map2)) return true;
        }
        return false;
    }

    // 初始化数组哈希
    void initMap(int[] map, char[] chs, int len) {
        for (int i = 0; i < len; i ++) {
            map[chs[i] - 'a'] ++;
        }
    }

    // 判断数组哈希是否一致
    boolean check(int[] map1, int[] map2) {
        for (int i = 0; i < map1.length; i ++) {
            if (map1[i] != map2[i]) return false;
        }
        return true;
    }
}