首页 > 试题广场 >

找到字符串中的异位词

[编程题]找到字符串中的异位词
  • 热度指数:650 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定两个字符串 s 和 p ,请你找到 s 子数组中的全部 p 的异位词的起始点。异位词值可以通过重新排列字符顺序(或者不排列)而相等的词。
你可以以任意顺序返回

数据范围: s 和 p 的长度满足 ,字符串中仅包含小写英文字母
示例1

输入

"cabac","abc"

输出

[0,2]
示例2

输入

"ababab","ab"

输出

[0,1,2,3,4]
public ArrayList<Integer> findWord (String s, String p) {
        // write code here
        int[] arr=new int[26];
        for(char c : p.toCharArray()){
            arr[c-'a']+=1;
        }
        
        int i=0;
        ArrayList<Integer> res=new ArrayList<>();
        for(int j=0;j<s.length();j++){
            char c = s.charAt(j);
            arr[c-'a']-=1;
            while(arr[c-'a']<0 && i>=0 && i<s.length()){
                char pre=s.charAt(i);
                arr[pre-'a']+=1;
                i++;
            }
            if(j-i+1==p.length()){
                res.add(i);
            }
        }
        return res;
    }


发表于 2022-12-06 22:39:39 回复(0)