找到字符串中所有字母异位词

作者：Grey

原文地址：找到字符串中所有字母异位词

题目描述

LeetCode 438. 找到字符串中所有字母异位词

主要思路

使用滑动窗口和欠账表的机制，首先，将p串建立词频表

        int c = pStr.length;
        for (char ch : pStr) {
    
            map[ch - 'a']++;
        }

用于查询s串中还欠p串的元素种类和个数是多少。总共欠的字符个数是c。

接下来建立滑动窗口，在s串中设置l和r两个指针，先移动r，如果r位置的字符正好是p中的字符，说明这是一次有效还款，则c--，r继续移动，如果每次都是有效还款，则c必减为0，此时，就可以收集答案了，当r - l的长度正好是p串的长度时候，则说明必须以l位置的窗口，已经判断完毕了，接下来，可以移动l指针，开始缩窗口。如果l缩的位置正好是有效位置，则c++（因为l的旧位置已经不属于当前窗口了）。

时间复杂度O(N)。

完整代码

public class LeetCode_0438_FindAllAnagramsInAString {
    
    // 滑动窗口 + 欠账表
    public List<Integer> findAnagrams(String s, String p) {
    
        if (s == null || p == null) {
    
            return new ArrayList<>();
        }
        List<Integer> ans = new ArrayList<>();
        char[] str = s.toCharArray();
        char[] pStr = p.toCharArray();
        // 词频表
        int[] map = new int[26];
        // 窗口从[l,r)
        int l = 0;
        int r = 0;
        // 欠账数量
        int c = pStr.length;
        for (char ch : pStr) {
    
            map[ch - 'a']++;
        }
        int n = str.length;
        while (r < n) {
    
            if (map[str[r] - 'a'] > 0) {
    
                // 有效还款
                c--;
            }
            map[str[r++] - 'a']--;
            if (c == 0) {
    
                // 收集到一个位置
                ans.add(l);
            }
            // 形成窗口
            if (r - l == pStr.length) {
    
                // l面临要出窗口
                if (map[str[l] - 'a'] >= 0) {
    
                    // 退回去
                    c++;
                }
                map[str[l++] - 'a']++;
            }
        }
        return ans;
    }
}

类似问题

滑动窗口最大值问题

最小覆盖子串问题

更多

算法和数据结构笔记