leetcode 438. 找到字符串中所有字母异位词(优质解法)

2023-12-14 22:51:40

题解:

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> integerList=new ArrayList<>();    //用于记录最终答案
        //将 s 和 p 字符串转换为字符数组,方便讨论
        char []charS=s.toCharArray();
        char []charP=p.toCharArray();
        int pLength=p.length();
        int sLength=s.length();

        int []hash1=new int[26];    //用于记录 p 字符串中每个字符出现的个数
        int []hash2=new int[26];    //用于记录讨论的子串中每个字符出现的个数

        int count=0;    //符合条件的字符个数

        //将 p 字符串中的每一个字符出现的个数记录下来
        for (int i=0;i<pLength;i++){
            char c=charP[i];
            hash1[c-'a']++;
        }

        for(int left=0,right=0;right<sLength;right++){
            //记录 right 指针指向的字符
            int in=charS[right]-'a';
            hash2[in]++;
            //判断当前记录的字符是否是有效字符
            if(hash2[in]<=hash1[in]){
                count++;
            }
            //判断当前讨论的子串长度是否超过 p 字符串的长度
            if(right-left+1>pLength){
                int out=charS[left]-'a';
                //判断出窗口的字符是否是有效字符
                if(hash2[out]<=hash1[out]){
                    count--;
                }
                hash2[out]--;
                left++;
            }

            if(count==pLength){
                integerList.add(left);
            }
        }

        return integerList;
    }
}

题解:

? ? ? ? 首先本题题意很清晰,不需要过多解释

? ? ? ? 在看到一个题时,可以先想一下它的暴力解法,本题我们可以遍历出所有的子串,然后判断子串和 p 字符串是否是异位词(是否由相同的字符串组成),然后取每个子串第一位字符的下标即可

? ? ? ? 我们首先要考虑一个问题,如何判断子串和 p 字符串是否是异位词(是否由相同的字符串组成),我们可以通过 hash 表,记录 p 字符串中每个字符出现的次数和子串中每个字符出现的次数,进行比对,我们便知道两个字符串是否由相同字符组成

? ? ? ? 对于示例1进行分析

????????输入: s = "cbaebabacd", p = "abc"

? ? ? ? 让 L 和 R 指针指向下标为 0 的位置(因为我们要遍历所有的子串,所以从下标 0 开始), hash1 表记录 p 字符串所包含的字符个数count 变量记录当前子串有效字符的个数,a-1,b-1,c-1 ,将 R 指针指向的字符添加到 hash2 表中,key=c,value=1,由于 hash1 表中 c 字符对应的 value 值为 1,表示当前的 c 字符是有效字符 count+1,让 R 指针向右移

c????????b????????a????????e????????b????????a????????b????????a????????c????????d

L

R

? ? ? ? R 指针移动到当前位置时,子串的长度等于 p 字符串的长度,并且有效字符个数 count = 3 = p.length ,代表子串中的所有字符都是有效字符,所以当前的子串和 p 字符串就是异位词,记录当前 L 指针指向的下标

c????????b????????a????????e????????b????????a????????b????????a????????c????????d

L

? ? ? ? ? ? ? ? ? ? R

? ? ? ? 将 R 指针向右移动,此时子串的长度 right - left + 1 = 4 >?p.length,代表以 L 指针指向的字符为首的字符串已经遍历完毕,让 L 指针向右移动,并在 hash2 中将字符 b 对应的 value 值减 1 ,由于字符 c?对应的 value 值为 1 ,小于等于 hash1 中字符 b 对应的 value 值,所以字符 c 是关键字符,在将 L 指针移动以后,要将关键字符数量 count 减 1

????????此处涉及到一个问题,下一轮 R 指针需要回到 L 指针所在的位置从头开始遍历子串吗,答案是不需要,因为 R 指针到当前位置后才出现了长度不符合要求的子串,说明 R 指针和 L 指针之间的子串是符合长度要求的(不包括 R 指针指向的字符),所以将 R 指针移到 L 指针所在的位置,R 指针也会慢慢移动回来

c????????b????????a????????e????????b????????a????????b????????a????????c????????d

? ? ? ? ? L

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? R

? ? ? ??

????????

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