Find all alphabetic words in the string

author ：Grey

Original address ： Find all alphabetic words in the string

Title Description

LeetCode 438. Find all alphabetic words in the string

Main idea

Use Sliding windows and debt statements The mechanism of , First , take p String to establish word frequency table

        int c = pStr.length;
        for (char ch : pStr) {
    
            map[ch - 'a']++;
        }

Used for query s There is still... In the string p What is the type and number of elements in the string . The total number of characters owed is c.

Next, create a sliding window , stay s Set in the string l and r Two pointers , Move first r, If r The character of the position is exactly p The characters in , Explain that this is an effective repayment , be c--,r Keep moving , If the repayment is effective every time , be c Must be reduced to 0, here , You can collect the answers , When r - l It's exactly the length of p The length of the string , Then it must be stated in l Position window , It has been judged , Next , Can be moved l The pointer , Start shrinking the window . If l The retracted position is exactly the effective position , be c++（ because l The old position of no longer belongs to the current window ）.

Time complexity O(N).

Complete code

public class LeetCode_0438_FindAllAnagramsInAString {
    
    //  The sliding window  +  Balance sheet 
    public List<Integer> findAnagrams(String s, String p) {
    
        if (s == null || p == null) {
    
            return new ArrayList<>();
        }
        List<Integer> ans = new ArrayList<>();
        char[] str = s.toCharArray();
        char[] pStr = p.toCharArray();
        //  word frequency list 
        int[] map = new int[26];
        //  Window from [l,r)
        int l = 0;
        int r = 0;
        //  Amount in arrears 
        int c = pStr.length;
        for (char ch : pStr) {
    
            map[ch - 'a']++;
        }
        int n = str.length;
        while (r < n) {
    
            if (map[str[r] - 'a'] > 0) {
    
                //  Effective repayment 
                c--;
            }
            map[str[r++] - 'a']--;
            if (c == 0) {
    
                //  Collect to a location 
                ans.add(l);
            }
            //  Form a window 
            if (r - l == pStr.length) {
    
                // l Facing the window 
                if (map[str[l] - 'a'] >= 0) {
    
                    //  Go back to 
                    c++;
                }
                map[str[l++] - 'a']++;
            }
        }
        return ans;
    }
}

Similar problems

Sliding window maximum problem

Minimum covering substring problem

more

Algorithm and data structure notes