526互联

LeetCode567. 字符串的排列

发布时间 2023-12-04 14:50:44作者: Ac_c0mpany丶

题目描述

image.png

思路：滑动窗口模板

  • 定义需要维护的变量
Map<Character, Integer> map = new HashMap<>();
Map<Character, Integer> map_s1 = new HashMap<>();
for (char c : s1.toCharArray()) {
	map_s1.put(c, map_s1.getOrDefault(c, 0) + 1);
}
  • 根据题意可知：窗口为固定大小所以用if
 if (end - start + 1 == s1.length()) {
	char startChar = s2.charAt(start);
	map.put(startChar, map.get(startChar) - 1);
	if (map.get(startChar) == 0) {
		map.remove(startChar);
	}
	start ++;
}

方法一：

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        // 1. 定义需要维护的变量
        Map<Character, Integer> map = new HashMap<>();
        Map<Character, Integer> map_s1 = new HashMap<>();
        for (char c : s1.toCharArray()) {
            map_s1.put(c, map_s1.getOrDefault(c, 0) + 1);
        }

        // 2. 定义窗口边界
        int start = 0;
        for (int end = 0; end < s2.length(); end ++) {
            // 3. 更新需要维护的变量
            char currentChar = s2.charAt(end);
            map.put(currentChar, map.getOrDefault(currentChar, 0) + 1);
            if (map.equals(map_s1)) {
                return true;
            }
            if (end - start + 1 == s1.length()) {
                char startChar = s2.charAt(start);
                map.put(startChar, map.get(startChar) - 1);
                if (map.get(startChar) == 0) {
                    map.remove(startChar);
                }
                start ++;
            }
        }
        return false;
    }
}