.leetcode(438. Find All Anagrams in a String)

문제

https://leetcode.com/problems/find-all-anagrams-in-a-string/

문제 풀기 전

1. 예전에 문제중에 이런걸 키로 만들어 카운트 했떤 문제의 아이디를 빌어서 키로 만들고 풀기
2. 아니면 정렬하기 O(logN * n)
3. 우선 변환하고 풀면 O(N*26)
4. 혹시 trie로 풀 수 있지 않을까

직접 푼 풀이

소요시간: 15분(17:08 ~ 17:23, 정렬을 이용한 풀이) 4분(17:25 ~ 17:29, 키를 이용한 풀이)

# 정렬을 이용한 풀이
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        char[] keywords = p.toCharArray();
        Arrays.sort(keywords);

        List<Integer> ret = new ArrayList<>();
        for (int i=0; i<s.length()-p.length()+1; i++) {
            char[] compare = s.substring(i, i+p.length()).toCharArray();
            Arrays.sort(compare);

            if (String.valueOf(compare).equals(String.valueOf(keywords))) {
                ret.add(i);
            }
        }

        return ret;
    }
}

# 키를 이용한 풀이
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        String keywords = convertToKey(p);

        List<Integer> ret = new ArrayList<>();
        for (int i=0; i<s.length()-p.length()+1; i++) {
            String compare = convertToKey(s.substring(i, i+p.length()));


            if (compare.equals(keywords)) {
                ret.add(i);
            }
        }

        return ret;
    }

    private String convertToKey(String target) {
        int[] box = new int[26];
        for(int i=0; i<target.length(); i++) {
            box[(target.charAt(i)-'a')]++; 
        }

        StringBuilder builder = new StringBuilder();
        for (int i=0; i<26; i++) {
            builder.append(box[i]+",");
        }

        return builder.toString();
    }
}

# 전체를 키로 먼저 변환하고 변환된 키끼리 비교
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        if (s.length() < p.length()) {
            return new ArrayList<>();
        }

        String keywords = convertToKey(p);

        List<Integer> ret = new ArrayList<>();

        List<String> converted = convertToKey(s, p.length());
        int count=0;
        for (String compare: converted) {
            if (compare.equals(keywords)) {
                ret.add(count);
            }
            count++;
        }

        return ret;
    }

    private String convertToKey(String target) {
        int[] box = new int[26];
        for(int i=0; i<target.length(); i++) {
            box[(target.charAt(i)-'a')]++; 
        }

        StringBuilder builder = new StringBuilder();
        for (int i=0; i<26; i++) {
            builder.append(box[i]+",");
        }

        return builder.toString();
    }

    private List<String> convertToKey(String target, int size) {
        int[] prev = new int[size];
        int[] box = new int[26];
        for (int i=0; i<size-1; i++) {
            prev[i] = (target.charAt(i)-'a');
            box[(target.charAt(i)-'a')]++; 
        }

        List<String> ret = new ArrayList<>();
        for(int i=size-1; i<target.length(); i++) {
            box[(target.charAt(i)-'a')]++; 
            prev[i%size] = target.charAt(i)-'a';
            StringBuilder builder = new StringBuilder();
            for (int j=0; j<26; j++) {
                builder.append(box[j]+",");
            }
            ret.add(builder.toString());
            box[prev[(i+1)%size]]--;
        }


        return ret;
    }
}

느낀점

1. 역시 이런 anagram의 풀이는 정렬 혹은 키를 만드는것에서 부터 아이디어를 생각하면 잘 풀린다.
2. 슬라이딩의 아이디어도 엿볼 수 있다.

누적되는 알고리즘 접근 설명서

2021/01/09 - [알고리즘 풀이] - .leetcode(알고리즘 문제풀이 접근)