[C]Intuitive Solution with UTHASH and QSORT


  • 0
    H
    typedef struct hash_entry {
        char*key;
        int bkt_n;
        int chain_n;
        UT_hash_handle hh;
    }hash_entry;
    char str_dup[2048] = {0};
    int compare(const void*a, const void*b) {
        return *(char*)a - *(char*)b;
    }
    #define CHAIN_SIZE (100)
    char*** groupAnagrams(char** strs, int strsSize, int** columnSizes, int* returnSize) {
        struct hash_entry *hashtable = NULL, *tmp_node = NULL, *ptr;
        char*** ret_str = calloc(strsSize, sizeof(char*));
        *columnSizes = calloc(strsSize, sizeof(int));
        int bkt_n=0;
        *returnSize = 0;
    
        for(int strs_idx = 0; strs_idx < strsSize; strs_idx++) {
            const char*str_head = *(strs + strs_idx);
            int tgt_len = strlen(str_head);
            memcpy(str_dup, str_head, tgt_len+1);
            qsort(str_dup, tgt_len, 1, compare);
            HASH_FIND_STR(hashtable, str_dup, tmp_node);
            if(tmp_node == NULL) {
                //create_new hash
                ptr = malloc(sizeof(hash_entry));
                ptr->key = malloc(tgt_len+1);
                ptr->bkt_n = bkt_n++;
                ptr->chain_n = 0;
                memcpy(ptr->key, str_dup, tgt_len+1);
                HASH_ADD_STR(hashtable, key, ptr); 
                tmp_node = ptr;
                *(ret_str + tmp_node->bkt_n) = malloc(sizeof(char*) * CHAIN_SIZE);
                *returnSize += 1;
            } else {
                ptr->chain_n++;
            }
            //add to a created entry
            *((*(ret_str + tmp_node->bkt_n)) + (*columnSizes)[tmp_node->bkt_n]) = malloc(tgt_len+1);
            memcpy(*((*(ret_str + (tmp_node->bkt_n))) + (*columnSizes)[tmp_node->bkt_n]), str_head, tgt_len+1);
            (*columnSizes)[(tmp_node->bkt_n)] += 1;
        }
        return ret_str;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.