字符串中的所有变位词

发布时间:2023年12月31日

????????这道算法题是字符串中的变位词的变种,思路都大差不差,一样可以用一个数组来模拟哈希表去统计字母出现的次数,然后与0比较。

? ? ? ? 同样的,也可以用两个数组去分别统计,然后比较两个数组是否相同。先形成初始窗口,然后去维护这个滑动窗口。维护时使用两个指针,指针i从s2.length()索引开始,逐步加入字母(对应位置加1),指针i-s2.length()从0索引开始,逐步删除字母(对应位置减1)。

    public static List<Integer> findAnagrams2(String s1, String s2) {
        // 获取字符串长度
        int m = s1.length();
        int n = s2.length();

        // 如果s1的长度小于s2,无法找到变位词,直接返回空列表
        if (m < n) return new ArrayList();

        // 用于记录每个字母出现次数的数组
        int[] cnt1 = new int[26];  // 对应s1
        int[] cnt2 = new int[26];  // 对应s2

        // 用于存储找到的变位词的起始索引
        List<Integer> list = new ArrayList<>();

        // 初始化前n个字符的字母出现次数
        for (int i = 0; i < n; i++) {
            cnt1[s1.charAt(i) - 'a']++;
            cnt2[s2.charAt(i) - 'a']++;
        }

        // 检查前n个字符形成的子串是否为变位词
        if (Arrays.equals(cnt1, cnt2)) list.add(0);

        // 使用滑动窗口从第n个字符开始遍历s1
        for (int i = n; i < m; i++) {
            // 更新窗口内的字母出现次数
            cnt1[s1.charAt(i) - 'a']++;
            cnt1[s1.charAt(i - n) - 'a']--;

            // 检查当前子串是否为变位词
            if (Arrays.equals(cnt1, cnt2)) list.add(i - n + 1);
        }
        return list;
    }

初始化阶段(前n个字符):时间复杂度是O(n),滑动窗口阶段(从第n个字符开始):时间复杂度是O(m - n),因此,整个算法的时间复杂度是 O(n + m - n) = O(m)。另外我们使用了两个常数大小的数组,使用空间复杂度是O(1)。

文章来源:https://blog.csdn.net/w17319185551/article/details/135308236
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。