DX's Digital Garden

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

3 min read

  • 2.25

    • 字典的长度为 26，而不是两个字符串各自的长度
    • for 循环时，循环结束条件时 s 的长度-p 的长度
    • 记得开头健壮性判断

  • 2.6

    • 将窗口放进数组做字典，看字典是否相同
    • 在开始移动时，需要注意窗口的移动距离：s 的长度➖p 的长度，窗口的右半部分是i+p.length
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        if(p.length()>s.length()) return res;
        int[] dict = new int[26];
        int[] window = new int[26];
        for(int i=0;i<p.length();i++){
            dict[p.charAt(i)-'a']++;
            window[s.charAt(i)-'a']++;
        }
        if(Arrays.equals(dict,window)) res.add(0);
 
        for(int i=0;i<s.length()-p.length();i++){
            window[s.charAt(i)-'a']--;
            window[s.charAt(i+p.length())-'a']++;
            if(Arrays.equals(window,dict)) res.add(i+1);
        }
        return res;
    }
}
  • 1.22
    • 这道题需要先放第一个窗口
    • 之后固定窗口尺寸往前移 ​
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        if(s.length()<p.length()) return res;
        int[] source = new int[26];
        int[] tartge = new int[26];
 
        for(int i=0;i<p.length();i++){
            source[s.charAt(i)-'a']++;
            tartge[p.charAt(i)-'a']++;
        }
        if(Arrays.equals(source,tartge)) res.add(0);
 
        for(int i=0;i<s.length()-p.length();i++){
            source[s.charAt(i)-'a']--;
            source[s.charAt(i+p.length())-'a']++;
            if(Arrays.equals(source,tartge)) res.add(i+1);
        }
        return res;
 
    }
}
  • 1.11
    • 判断是否 s 和 p 长度符合常理
    • 先创造两个指纹库，然后录入两个数组内对应字母的指纹库
      • 先填充第一个窗口（按 p 的长度来），判断是否相等是否添加结果
      • 之后进行 for 循环判断，移除前一个窗口，添加后一个窗口，注意：如果相等，添加的是 left+1 的窗口,因为 left 是上一轮的窗口起点，踢掉之后新的窗口起点是 left+1；
      • 模板指纹库，在初始化时后面就不用动了，for 循环里移动的是 s 指纹库
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        if(s.length()<p.length()) return res;
        int[] numS = new int[26];
        int[] numP = new int[26];
        for(int i=0;i<p.length();i++){
            numS[s.charAt(i)-'a']++;
            numP[p.charAt(i)-'a']++;
        }
        if(Arrays.equals(numS,numP)) res.add(0);
        for(int left =0;left<s.length()-p.length();left++){
            numS[s.charAt(left)-'a']--;
            numS[s.charAt(left+p.length())-'a']++;
            if(Arrays.equals(numS,numP)) res.add(left+1);
        }
        return res;
    }
}
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        if(s.length()<p.length()) return res;
        int[] numS = new int[26];
        int[] numP = new int[26];
        for(int i=0;i<p.length();i++){
            numS[s.charAt(i)-'a']++;
            numP[p.charAt(i)-'a']++;
        }
        if(Arrays.equals(numP,numS)) res.add(0);
        for(int left=0;left<s.length()-p.length();left++){
            numS[s.charAt(left)-'a']--;
            numS[s.charAt(left+p.length())-'a']++;
            if(Arrays.equals(numP,numS)) res.add(left+1);
        }
        return res;
    }
}
  • 哨兵判断
  • 用数组存窗口 int[]
  • 窗口的初始化
  • 再次判断
  • 真正开始滑动窗口
  • 数组下的窗口移动
numS[s.charAt(left)-'a']--;
numS[s.charAt(left+p.length())-'a']++;
  • ArraysAPI的调用

Graph View