leetcode [#438]

目录

• 1. 题目
• 2. 解决方案
• 3. 注意事项

题目

Given a string s and a non-empty string p, find all the start indices of p’s anagrams in s.
Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.
The order of output does not matter.

Example1:
Input:
s: “cbaebabacd” p: “abc”

Output:
[0, 6]

Explanation:
The substring with start index = 0 is “cba”, which is an anagram of “abc”.
The substring with start index = 6 is “bac”, which is an anagram of “abc”.

Example2:
Input:
s: “abab” p: “ab”

Output:
[0, 1, 2]

Explanation:
The substring with start index = 0 is “ab”, which is an anagram of “ab”.
The substring with start index = 1 is “ba”, which is an anagram of “ab”.
The substring with start index = 2 is “ab”, which is an anagram of “ab”.

---

解决方案

public class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> list = new LinkedList<>();
        if (p == null || s == null || s.length() < p.length()) return list;
        int pLen = p.length();
        int sLen = s.length();

        for(int i = 0 ; i + pLen -1 < sLen; i++){
            String cur = s.substring(i, i + pLen);
            if (helper(cur, p)) list.add(i);
        }
        return list;
    }
    public static boolean helper(String a, String b) {
        if (a == null || b == null || a.length() != b.length()) return false;
        int[] dict = new int[26];
        for (int i = 0; i < a.length(); i++) {
            char ch = a.charAt(i);
            dict[ch-'a']++;
        }
        for (int i = 0; i < b.length(); i++) {
            char ch = b.charAt(i);
            dict[ch-'a']--;
            if (dict[ch-'a'] < 0) return false;
        }
        return true;
    }
}

---

注意事项

1. 遍历s字符串（以pLen为每段长度）
2. 准备数组int[] dict = new int[26];用于统计出现次数：在p中出现对应位加1，在s中出现对应位减1
3. 如果最后数组该位小于零，则说明片段未能对应，不是Anagrams；否则能对应