from 91 ms to 22 ms


  • 0
    X

    91m

    public class Solution {
        public boolean checkInclusion(String s1, String s2) {
            HashMap<Character, Integer> target = new HashMap<>();
            for(char ch : s1.toCharArray()){
                target.putIfAbsent(ch, 0);
                target.put(ch, target.get(ch) + 1);
            }
            HashMap<Character, Integer> current = new HashMap<>();
            for(int i = 0 ; i < s2.length() ; i++){
                char cur = s2.charAt(i);
                current.putIfAbsent(cur, 0);
                current.put(cur, current.get(cur) + 1);
                if(i >= s1.length()){
                    char del = s2.charAt(i - s1.length());
                    current.put(del, current.get(del) - 1);
                    if(current.get(del) == 0) current.remove(del);
                }
                if(current.equals(target)) return true;
            }
            
            return false;
        }
    }
    

    I am using hashmap.equals function which means for every sliding window, all 26 characters will be compared, but in fact, only the count of 2 characters may change, so the improved solution:

    public class Solution {
        public boolean checkInclusion(String s1, String s2) {
            int[] cnt1 = new int[26];
            int[] cnt2 = new int[26];
            if(s1.length() > s2.length()) return false;
            for(int i = 0 ; i < s1.length() ; i++){
                cnt1[s1.charAt(i) - 'a']++;
                cnt2[s2.charAt(i) - 'a']++;
            }
            
            int cnt = 0;
            for(int i = 0;i < 26;i++){
                if(cnt1[i] == cnt2[i]) cnt++;
            }
            if(cnt == 26) return true;
            
            for(int i = s1.length();i < s2.length();i++){
                char del = s2.charAt(i - s1.length());
                char add = s2.charAt(i);
                if(cnt1[del - 'a'] == cnt2[del - 'a']) cnt--;
                if(cnt1[add - 'a'] == cnt2[add - 'a']) cnt--;
                cnt2[del - 'a']--;
                cnt2[add - 'a']++;
                if(cnt1[del - 'a'] == cnt2[del - 'a']) cnt++;
                if(cnt1[add - 'a'] == cnt2[add - 'a']) cnt++;
                if(cnt == 26) return true;
            }
            
            return false;
        }
    }
    

Log in to reply
 

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