567. 字符串的排列
题意：
第一个字符串的排列之一是第二个字符串的子串即判断第二个字符串是否包含某个子串，这个子串的字符以及字符数量要求与第一个字符串相同解法1 (暴力法)
按照第一个字符串的长度找出第二个字符串的所有相应长度的子串比较每个子串与第一个字符串的字符以及字符数量是否相同 (哈希表)class Solution {public static boolean checkInclusion(String s1, String s2) {Map<Character, Integer> map1 = new HashMap<>();Map<Character, Integer> map2 = new HashMap<>();map1 = countChar(s1);for (int start = 0; start < s2.length(); start++) {map2.clear();int end;if ((end = start + s1.length() - 1) > s2.length() - 1) break;map2 = countChar(s2.substring(start, end + 1));if (map2.equals(map1)) return true;}return false;}public static Map<Character, Integer> countChar(String s) {Map<Character, Integer> map = new HashMap<>();for (int i = 0; i < s.length(); i++) {if (map.containsKey(s.charAt(i))) {map.put(s.charAt(i), map.get(s.charAt(i)) + 1);} else {map.put(s.charAt(i), 1);}}return map;} }
解法2 (滑动窗口)
class Solution {public static boolean checkInclusion(String s1, String s2) {Map<Character, Integer> map1 = new HashMap<>();Map<Character, Integer> map2 = new HashMap<>();map1 = countChar(s1);int start = 0;for (int end = 0; end < s2.length(); end++) {map2.put(s2.charAt(end), map2.getOrDefault(s2.charAt(end), 0) + 1);while (findAll(map1, map2)) {if (map2.equals(map1)) return true;map2.put(s2.charAt(start), map2.get(s2.charAt(start)) - 1);if (Integer.valueOf(0).equals(map2.get(s2.charAt(start)))) map2.remove(s2.charAt(start));start++;}}return false;}public static boolean findAll(Map<Character, Integer> map1, Map<Character, Integer> map2) {Set<Map.Entry<Character, Integer>> set = map1.entrySet();for (Map.Entry<Character, Integer> entry : set) {if (entry.getValue() > map2.getOrDefault(entry.getKey(), 0)) return false;}return true;}public static Map<Character, Integer> countChar(String s) {Map<Character, Integer> map = new HashMap<>();for (int i = 0; i < s.length(); i++) {map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);}return map;} }
