题目
给你两个字符串 s1 和 s2 ,写一个函数来判断 s2 是否包含 s1 的排列。如果是,返回 true ;否则,返回 false 。
换句话说,s1 的排列之一是 s2 的 子串 。
示例
示例 1:
输入:s1 = “ab” s2 = “eidbaooo”
输出:true
解释:s2 包含 s1 的排列之一 (“ba”).
示例 2:
输入:s1= “ab” s2 = “eidboaoo”
输出:false
思路1:dfs
使用集合统计s1的所有可能排列结果,然后挨个遍历,看是否在s2中
- 简单粗暴
- 容易超时
思路2:滑动窗口
前提:abc排列结果集6种:[abc,acb,bca,bac,cab,cba]。但是无论怎么排列,6种结果集中,一定是根据元素abc三个字符排列的。
所以,如果s1 = “abc”,我们只要判断s2中长度 = 3(abc的长度)的subStr子串,是否有包含abc三个字符的。有则说明包括。
比如s2 = “bbbca”,其中长度为3的子串bca,就由abc三个字符组成。所以就包含
步骤:
1、确定s1的长度len
2、使用滑动窗口,在s2中,扩张到len
- 此时,s1
- s2的子串sub2
3、判断:s2的subStr子串,是否由s1中字符组成 :使用map判断
mapS1
- key:字符
- val:每个字符出现的次数
- abc:(a-1,b-1,c-1)
mapSub2
- key:字符
- val:每个字符出现的次数
- bbb(b-3)
如果mapS1中的所有key集合
key - v1
key - v2
都满足 v1 == v2,也就是说s1中的每个字符,都在sub2中,而且每个字符出现的频率和sub2一样,则说明s2的subStr子串,是由s1中字符组成的
4、举例:
s1:abc
s2:bbbca
- 第一个sub2:bbb,显然mapS1中(a-1,b-1,c-1),而mapS2中(b-3),不满足
- 窗口滑动得到第二个sub2:bbc,显然mapS2中(b-2,c-1),不满足
- 窗口滑动得到第三个sub2:bca,显然mapS2中(b-1,c-1,a-1),满足。
和mapS1中每个元素,对应的val值(出现频率)都一样。说明找到了!
public class CheckS1PermuteInS2 {public static void main(String[] args) {boolean b = checkInclusion("ab", "eidboaoo");System.out.println(b);}public static boolean checkInclusion(String s1, String s2) {if (s1 == null || s1.length() == 0) {return true;}if (s2 == null || s2.length() == 0 || s2.length() < s1.length()) {return false;}if (s1.length() == 1) {return s2.contains(s1);}Map<Character, Integer> mapS1 = new HashMap<>();int len1 = s1.length();for (int i = 0; i < len1; i++) {mapS1.merge(s1.charAt(i), 1, Integer::sum);}// 扩张到len1 - 1int i = 0;Map<Character, Integer> mapS2 = new HashMap<>();while (i < s1.length() - 1) {mapS2.merge(s2.charAt(i), 1, Integer::sum);i++;}i = 0;for (int j = len1 - 1; j < s2.length(); j++) {mapS2.merge(s2.charAt(j), 1, Integer::sum);if (contain(mapS1, mapS2)) {return true;} else {// 滑动char start = s2.charAt(i);Integer v2 = mapS2.get(start);mapS2.put(start, v2 - 1);i++;}}return false;}private static boolean contain(Map<Character, Integer> mapS1, Map<Character, Integer> mapS2) {Set<Character> s1Keys = mapS1.keySet();for (Character s1Key : s1Keys) {Integer v1 = mapS1.get(s1Key);Integer v2 = mapS2.get(s1Key);if (Objects.equals(v1, v2)) {return false;}}return true;}
}