给你两个字符串 s1
和 s2
,写一个函数来判断 s2
是否包含 s1
的排列。如果是,返回 true
;否则,返回 false
。
换句话说,s1
的排列之一是 s2
的 子串 。
示例 1:
输入:s1 = "ab" s2 = "eidbaooo" 输出:true 解释:s2 包含 s1 的排列之一 ("ba").
示例 2:
输入:s1= "ab" s2 = "eidboaoo" 输出:false
提示:
1 <= s1.length, s2.length <= 104
s1
和s2
仅包含小写字母
class Solution { public boolean checkInclusion(String s1, String s2) { HashMap<Character, Integer> window = new HashMap<>(); HashMap<Character, Integer> need = new HashMap<>(); for (char c : s1.toCharArray()) { need.put(c, need.getOrDefault(c, 0) + 1); } int left = 0, right = 0; int valid = 0; while (right < s2.length()) { char c = s2.charAt(right); right++; if (need.containsKey(c)) { window.put(c, window.getOrDefault(c, 0) + 1); //包装类需要使用equals判断是否相等 if (window.get(c).equals(need.get(c))) valid++; } //System.out.println("window: [" + left + "," + right + ")"); if (right - left == s1.length()) { if (valid == need.size()) { return true; } char d = s2.charAt(left); left++; if (need.containsKey(d)) { //只有先判断相等valid才能减1 if (window.get(d).equals(need.get(d))) valid--; window.put(d, window.get(d) - 1); } } } return false; } }
标签:排列,s2,s1,567,need,window,right,字符串,valid From: https://www.cnblogs.com/Co3y/p/17276281.html