剑指offer专项突击版 ---第 5 天

剑指offer专项突击版 ---第 5 天

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();
        if(m > n){
            return false;
        }
        int[] arr1 = new int[26];
        int[] arr2 = new int[26];
        for(int i = 0; i < m; i++){
            ++arr1[s1.charAt(i) - 'a'];
            ++arr2[s2.charAt(i) - 'a'];
        }
        if(Arrays.equals(arr1,arr2)){
            return true;
        }
        for(int j = m; j < n; j++){
            ++arr2[s2.charAt(j) - 'a'];
            --arr2[s2.charAt(j - m) - 'a'];
            if(Arrays.equals(arr1,arr2)){
                return true;
            }
        }
        return false;
    }
}

class Solution {
    public List findAnagrams(String s, String p) {
        List list = new ArrayList<>();
        int m = s.length();
        int n = p.length();
        if(n > m){
            return list;
        }
        int[] arr1 = new int[26];
        int[] arr2 = new int[26];
        for(int i = 0; i < n; i++){
            ++arr1[s.charAt(i) - 'a'];
            ++arr2[p.charAt(i) - 'a'];
        }
        if(Arrays.equals(arr1,arr2)){
            list.add(0);
        }
        for(int j = n; j < m; j++){
            ++arr1[s.charAt(j) - 'a'];
            --arr1[s.charAt(j - n) - 'a'];
            if(Arrays.equals(arr1,arr2)){
               list.add(j - n + 1);
            }
        }
        return list;

    }
}

class Solution {
    public int lengthOfLongestSubstring(String s) {
        HashMap calc = new HashMap<>();
        int left = 0;
        int ret = 0;
        for(int i = 0; i < s.length(); i++){
            if(calc.containsKey(s.charAt(i))){
                left = Math.max(left, calc.get(s.charAt(i)) + 1);
            }
            calc.put(s.charAt(i),i);
            ret = Math.max(ret,i -left + 1);
        }
        return ret;
    }
}