Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Topic describes

Given two strings s and p, find substrings of all p’s allotopic words in S and return the starting index of these substrings. Regardless of the order in which the answers are printed.

An allotopic word is a string in which the letters are the same but arranged differently.

Example 1: Input: s = "cbaebabacd", p = "ABC" Output: [0,6] Explanation: The substring whose starting index is 0 is "CBA ", which is an allotopic of" ABC ". The substring whose starting index is 6 is "bac", which is an allotopic of "ABC". Source: LeetCode Link: https://leetcode-cn.com/problems/find-all-anagrams-in-a-string Copyright belongs to The Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.Copy the code

Thought analysis

  • Today’s algorithm problem of the day is solving an allotopic word, which is a string of characters that have the same letters but are arranged differently.
  • We solve the problem of heterotopic words, generally using ASCII knowledge, through arrays to store the number of occurrences of characters.
  • First count the number of characters appearing in P, then dynamically update the number of characters appearing in S, and compare the CNT array to get the answer.

Through the code

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ans = new ArrayList<>();
        int n = s.length();
        int m = p.length();
        if (n < m) {
            return ans;
        }

        int[] sCnt = new int[26];
        int[] pCnt = new int[26];
        for (int i = 0; i < m; i++) {
            sCnt[s.charAt(i) - 'a'] + +; pCnt[p.charAt(i) -'a'] + +; }if (Arrays.equals(sCnt, pCnt)) {
            ans.add(0);
        }

        for (int i = m; i < n; i++) {
            sCnt[s.charAt(i) - 'a'] + +; sCnt[s.charAt(i - m) -'a']--;
            if (Arrays.equals(sCnt, pCnt)) {
                ans.add(i - m + 1); }}returnans; }}Copy the code

conclusion

  • The time complexity of this algorithm is O(n), the space complexity is O(n).
  • Adhere to the algorithm of the day, come on!