找到所有字符异位词

冷不防 2022-10-29 07:58 110阅读 0赞

/** * 找到所有字符异位词 * 给定一个字符串s和一个非空字符串t，找到s中所有是t的字符异位词的子串，并返回这些子串的所有索引 */
    public class Solution3 { 
    
        public static void main(String[] args) { 
            String s = "cbaebabacd";
            String t = "abc";
            List<Integer> calc = calc(s, t);
            System.out.println(calc);
        }
    
        static List<Integer> calc(String s , String t) { 
            Map<Character, Integer> window = new HashMap<>();
            Map<Character, Integer> need = new HashMap<>();
            for (int i = 0; i < t.length(); i++) { 
                char c = t.charAt(i);
                need.put(c, need.getOrDefault(c, 0) + 1);
            }
            int left = 0;
            int right = 0;
            int valid = 0;
            List<Integer> rs = new ArrayList<>();
            while (right < s.length()) { 
                char r = s.charAt(right);
                if (need.get(r) != null) { 
                    window.put(r, window.getOrDefault(r, 0) + 1);
                    if (window.get(r) == need.get(r)) { 
                        valid++;
                    }
                }
                right++;
                while (right - left >= t.length()) { 
                    char l = s.charAt(left);
                    if (valid == need.size()) { 
                        rs.add(left);
                    }
    
                    if (need.get(l) != null) { 
                        if (window.get(l) == need.get(l)) { 
                            valid--;
                        }
                        window.put(l, window.getOrDefault(l, 0) - 1);
                    }
                    left++;
                }
            }
            return rs;
        }
    }