Java Sliding Window


  • 2
    S

    Idea is to keep a window of size p.length() and check if the substring is valid among the way.

    public class Solution {
        public List<Integer> findAnagrams(String s, String p) {
            List<Integer> res = new ArrayList<>();
            if(p.length() > s.length())
                return res;
            char[] sStr = s.toCharArray();
            int[]map = new int[26];
            for(char ch:p.toCharArray())
                map[ch - 'a']++;
            int n = s.length(), m = p.length();;
            int j = 0;
            for(j=0; j<m-1; j++)
                map[sStr[j] - 'a']--;
            for(int i=0; j<n; i++, j++){
                map[sStr[j] - 'a']--;
                if(check(map))
                    res.add(i);
                map[sStr[i] - 'a']++;
            }
            return res;
        }
        public boolean check(int[]map){
            for(int n:map)
                if(n > 0)   return false;
            return true;
        }
    }
    

  • 1
    Y

    how about the time complexity?


  • 0
    Z

    @yuhengw I think it is O(n), since 26 is a constant.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.