文章目录

• • 题目描述
  • 解题思路：

题目描述

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

解题思路：

方法一：求出p的所有字母异位的情况存储在hashset中，在s中使用滑动窗口的方法截取p长度的字符串，判断是否在hashset中，在则加入到答案。（但是好像是会超时）

方法二：使用数组的方式进行存储和判断，不是用求出所有的p的字母异位词，而是判断字母的个数，当在s中截取的字符串字母个数和种类个数与p中相同时，加入答案。

代码：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution438 {
    //    /*
//    思路：遍历出p的所有字母异位词，存放在哈希映射中，在s中使用移动窗口的方法遍历每段长度查看是否出现在映射中
//     */
//    public List<Integer> findAnagrams(String s, String p) {
//        int len = p.length();
//        HashSet<String> hashSet = new HashSet<>();
//
//        dfs(new boolean[len],new StringBuilder(),hashSet,p,0);
//
//        List<Integer> list = new ArrayList<>();
//        for(int i = 0;i <= s.length() - len;i++){
//            //截取一段字符串进行判断
//            String substr = s.substring(i,i + len);
//            if(hashSet.contains(substr)){
//                list.add(i);
//            }
//        }
//
//        return list;
//    }
//
//    //Backtracking
//    /**
//     *
//     * @param isUsed 标记这个位置的元素是否被使用过
//     * @param str 合成的字符串
//     * @param list  将所有合格的字母异位存放在这
//     * @param target 需要查找的字母异位目标字符串
//     * @param index 遍历到的元素下标
//     */
//    private void dfs(boolean []isUsed, StringBuilder str, HashSet<String> list, String target, int index){
//
//        if(target.length() < str.length()){
//            return;
//        }
//
//        //将合格的字符串加入
//        if(target.length() == str.length()){
//            list.add(str.toString());
//        }
        int i = index;
//        for(int i = 0;i < target.length();i++) {
//            if(isUsed[i]){
//                continue;
//            }
//            str.append(target.charAt(i));
//            isUsed[i] = true;
//            dfs(isUsed,str,list,target,index + 1);
//            str.deleteCharAt(str.length() - 1);
//            isUsed[i] = false;
            i = (i + 1) % target.length();
//        }
//    }

    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> list = new ArrayList<>();
        char []arr_p = p.toCharArray();
        Arrays.sort(arr_p);
        for(int i = 0;i < s.length() - p.length() + 1;i++){
            char []arr_s = s.substring(i,i + p.length()).toCharArray();
            Arrays.sort(arr_s);
            if(Arrays.equals(arr_p,arr_s)){
                list.add(i);
            }
        }
        return list;
    }
}

优化，每次不是整个截取s中的字符串，而是将末尾的移除和将新进入的加入，看代码：

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int sLen = s.length(), pLen = p.length();

        if (sLen < pLen) {
            return new ArrayList<Integer>();
        }

        List<Integer> ans = new ArrayList<Integer>();
        int[] sCount = new int[26];
        int[] pCount = new int[26];
        for (int i = 0; i < pLen; ++i) {
            ++sCount[s.charAt(i) - 'a'];
            ++pCount[p.charAt(i) - 'a'];
        }

        if (Arrays.equals(sCount, pCount)) {
            ans.add(0);
        }

        for (int i = 0; i < sLen - pLen; ++i) {
            --sCount[s.charAt(i) - 'a'];
            ++sCount[s.charAt(i + pLen) - 'a'];

            if (Arrays.equals(sCount, pCount)) {
                ans.add(i + 1);
            }
        }

        return ans;
    }
}