判断s是否存在一个子串是t的一种全排列

蔚落 2022-10-29 07:58 26阅读 0赞

/** * 字符串排列 * 输入两个字符串s和t，判断s是否包含t的排列，就是判断s是否存在一个子串是t的一种全排列 * */
    public class Solution2 { 
        public static void main(String[] args) { 
            String s = "helloworld";
            String t = "oow";
            System.out.println(calc(s, t));
        }
    
        static boolean 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;
            while (right < s.length()) { 
                // r是移入窗口的字符
                char r = s.charAt(right);
                // 处理窗口内的数据
                if (need.get(r) != null) { 
                    window.put(r, window.getOrDefault(r, 0) + 1);
                    if (need.get(r) == window.get(r)) { 
                        valid++;
                    }
                }
                right++;
    
                // 如果valid满足need的条件
                while (right - left >= t.length()) { 
                    // l是移出窗口的字符
                    char l = s.charAt(left);
                    // 处理窗口里的数据
                    if (valid == need.size()) return true;
                    if (need.get(l) != null) { 
                        if (window.get(l) == need.get(l)) { 
                            valid--;
                        }
                        window.put(l, window.getOrDefault(l, 0) - 1);
                    }
    
                    left++;
                }
            }
            return false;
        }
    }