567. Permutation in String

문제

https://leetcode.com/problems/permutation-in-string/description/

풀이

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        Map<Character, Integer> map1 = new HashMap<>();
        Map<Character, Integer> map2 = new HashMap<>();

        int window = s1.length();
        int lt = 0;

        for(char c : s1.toCharArray()) {
            map1.put(c, map1.getOrDefault(c, 0) + 1);
        }

        for(int rt = 0; rt < s2.length(); rt++) {
            char c = s2.charAt(rt);
            map2.put(c, map2.getOrDefault(c, 0) + 1);

            if(rt - lt + 1 > window) {
                char target = s2.charAt(lt);
                map2.put(target, map2.get(target) - 1);

                if(map2.get(target) == 0) {
                    map2.remove(target);
                }
                lt++;
            }

            if(map1.equals(map2)) return true;
        }
        return false; 
    }
}

• s1의 문자열 길이만큼 탐색하는 고정길이 슬라이딩 윈도우
• 고정길이 안에서 s1의 글자들이 전부 존재한다면, permutation한 것
  • Map을 이용해 카운팅해서 윈도우마다 같은지 비교
  • HashMap.equals()는 순서에 상관없이 두 맵의 key와 value가 모두 동일하면 true를 반환

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        Map<Character, Integer> map1 = new HashMap<>();
        Map<Character, Integer> map2 = new HashMap<>();

        for(char c : s1.toCharArray()) {
            map1.put(c, map1.getOrDefault(c, 0) + 1);
        }

        int window = s1.length();

        for(int i = 0; i < s2.length(); i++) {
            char c = s2.charAt(i);
            map2.put(c, map2.getOrDefault(c, 0) + 1);

            if(i >= window) {
                char target = s2.charAt(i - window);
                map2.put(target, map2.get(target) - 1);

                if(map2.get(target) == 0) {
                    map2.remove(target);
                }
            }

            if(map1.equals(map2)) {
                return true;
            }
        }
          return false;
    }
}