[Hackerrank in C] sherlock and anagrams

문제

https://www.hackerrank.com/challenges/sherlock-and-anagrams/problem?isFullScreen=true&h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=dictionaries-hashmaps

Sherlock and Anagrams | HackerRank

 

풀이

array 안의 모든 anagram의 pair 의 수를 구하는 문제이다.

여기서 중요한 포인트는 #pair = (count * (count-1))/2 이라는 점과 sorted("ba") = "ab" 라는 점이다.

따라서 qsort를 사용하면 anagram을 쉽게 비교할 수 있고, anagram의 수를 구한 뒤, n*(n-1)/2 를 해서 #pairs를 구하면 된다는 것이다.  

 

전체적인 풀이는 밑의 과정으로 이루어졌다: 

1. array안의 모든 substring 찾아

2. entry key 와 비교해, 있다면 entry.count++;

3. 없다면 entry에 추가

 

코드

int cmp(const void* a, const void* b) {
    return *(char*)a - *(char*)b;
}
typedef struct Entry {
    char* key; // substring
    int count;
}Entry;

int sherlockAndAnagrams(char* s) {
    // find all substrings
    // use sort to cmp substrings (sort("ba") = "ab")
    
    Entry* entries = NULL;
    int entry_size = 0;
    int sSize = strlen(s);
    
    for(int i=0; i<sSize; i++) {
        for(int j=i; j<sSize; j++) { // find each substring = s[i, j]
            int len = j-i+1;
            char* substr = malloc(len + 1);
            strncpy(substr, s+i, len);
            substr[len] = '\0';
            
            // sort
            qsort(substr, len, sizeof(char), cmp);
            
            int found = 0;
            for(int k =0; k< entry_size; k++) { // compare substring with all keys in entries
                if(strcmp(entries[k].key, substr) == 0) {
                    entries[k].count++;
                    found = 1;
                    break;
                }
            }
            if(!found) { // add to entries
                entries = realloc(entries, (entry_size + 1)*sizeof(Entry));
                
                entries[entry_size].key = substr;
                entries[entry_size].count = 1;
                entry_size++;
            } else {
                free(substr);
            }
        }
    }
    
    int total = 0 ;
    for(int i=0; i<entry_size; i++) {
        int n = entries[i].count;
        total += n * (n-1)/2; // pairs = n*(n-1)/2;
        free(entries[i].key);
    }
    return total;
}