526互联

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

发布时间 2023-11-09 11:50:22作者: BkDench

题目概述：给定字符串s，p，找到s字符串子串中所有p的异位词，返回该字串的起始位置。异位词：由相同字母组成。
解题思路：由于其给定了p，所以枚举s中和p长度相同的子串，并判断是否为p的异位词(将p和子串都进行排序处理，再使用equals判断)。需要注意的是java中的substring(i,j)方法，获取的是[i,j)左闭右开的子串，i和j都表示索引。另一种优化做法就是：维护一个长度为p.length()的滑动窗口，窗口中维护p和窗口中每种字母数量的差值，只需判断该差值是否为0即可判断是否为p的异位词。
时间复杂度：\(O(n)\)
代码：

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer>res = new ArrayList<>();
        char src[] = p.toCharArray();
        Arrays.sort(src);
        String pp = new String(src);
        int len = p.length();
        for(int i = 0; i <= s.length() - len; i ++){
            String str = s.substring(i,i + len);//第一个参数表示起始位置，第二个参数
            //表示终止位置(不包含该位置)
            char ss[] = str.toCharArray();
            Arrays.sort(ss);
            String sss = new String(ss);
            if(pp.equals(sss))res.add(i);
        }

        return res;
    }
}