iT邦幫忙

0

【LeetCode with C: A Series of Problem-Solving Techniques】-- Group Anagrams

leetcode
xianyu 2024-10-17 11:36:07 ‧ 251 瀏覽

  • 分享至 

  • xImage
    •  

Description

  1. Group Anagrams

Given an array of strings strs, group the
anagrams together. You can return the answer in any order.

Example 1:

Input: strs = ["eat","tea","tan","ate","nat","bat"]

Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Explanation:

There is no string in strs that can be rearranged to form "bat".
The strings "nat" and "tan" are anagrams as they can be rearranged to form each other.
The strings "ate", "eat", and "tea" are anagrams as they can be rearranged to form each other.
Example 2:

Input: strs = [""]

Output: [[""]]

Example 3:

Input: strs = ["a"]

Output: [["a"]]

Constraints:

1 <= strs.length <= 10^4
0 <= strs[i].length <= 100
strs[i] consists of lowercase English letters.

Answer & Explaining

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 定義一個結構來存儲異位詞組
typedef struct {
    int key[26];         // 26個字母的頻率作為鍵
    char** anagrams;     // 異位詞列表
    int size;            // 異位詞的數量
    int capacity;        // 異位詞列表的容量
} AnagramGroup;

// 比較兩個鍵是否相等（用於比較字母頻率陣列）
int keys_equal(int* key1, int* key2) {
    for (int i = 0; i < 26; i++) {
        if (key1[i] != key2[i]) {
            return 0;   // 如果兩個鍵的某個位置不相等，返回 0（表示不同）
        }
    }
    return 1;           // 所有位置相等，返回 1（表示相等）
}

// 計算字符串的字符頻率，並存儲在 key 陣列中
void calculate_key(char* str, int* key) {
    for (int i = 0; i < 26; i++) {
        key[i] = 0;     // 初始化 key 陣列，將所有字母的頻率設為 0
    }
    while (*str) {      // 遍歷字符串中的每個字符
        key[*str - 'a']++;  // 計算每個字符的頻率，並存儲到對應的 key 位置
        str++;          // 移動到下一個字符
    }
}

/**
 * 返回異位詞分組的動態數組，並且根據要求返回列大小和總組數。
 */
char*** groupAnagrams(char** strs, int strsSize, int* returnSize, int** returnColumnSizes) {
    // 初始容量為 100，之後會根據需要動態擴展
    int initialCapacity = 100;
    // 動態分配一個哈希表，用於存儲異位詞分組
    AnagramGroup* hashTable = (AnagramGroup*)malloc(initialCapacity * sizeof(AnagramGroup));
    int hashSize = 0;  // 異位詞組的數量
    
    // 初始化哈希表，將所有異位詞組的 size 和 capacity 設置為 0
    for (int i = 0; i < initialCapacity; i++) {
        hashTable[i].size = 0;
        hashTable[i].capacity = 0;
        hashTable[i].anagrams = NULL;  // 將異位詞列表初始化為空
    }

    for (int i = 0; i < strsSize; i++) {
        char* word = strs[i];  // 取得當前的字符串
        int key[26];           // 用來存儲當前字符串的字符頻率鍵
        calculate_key(word, key);  // 計算字符頻率鍵
        
        int found = 0;  // 用來標記是否在hash table中找到匹配的鍵

        // 嘗試在hash table中找到該鍵對應的異位詞組
        for (int j = 0; j < hashSize; j++) {
            if (keys_equal(hashTable[j].key, key)) {  // 如果鍵匹配
                found = 1;  // 找到匹配的異位詞組
                // 檢查當前異位詞組容量是否足夠
                if (hashTable[j].size == hashTable[j].capacity) {
                    hashTable[j].capacity = hashTable[j].capacity == 0 ? 2 : hashTable[j].capacity * 2;  // 動態擴展容量
                    hashTable[j].anagrams = (char**)realloc(hashTable[j].anagrams, hashTable[j].capacity * sizeof(char*));  // 重新分配memory
                }
                hashTable[j].anagrams[hashTable[j].size++] = strs[i];  // 將當前字符串加入異位詞組
                break;
            }
        }

        // 如果hash table中沒有找到匹配的鍵，則新增一個異位詞組
        if (!found) {
            // 檢查hash table的容量是否足夠，不夠就擴展容量
            if (hashSize == initialCapacity) {
                initialCapacity *= 2;  // hash table容量擴展為原來的兩倍
                hashTable = (AnagramGroup*)realloc(hashTable, initialCapacity * sizeof(AnagramGroup));  // 重新分配內存
            }
            // 將字符頻率鍵拷貝到新的異位詞組中
            memcpy(hashTable[hashSize].key, key, sizeof(int) * 26);
            // 初始化新的異位詞組，分配初始容量
            hashTable[hashSize].anagrams = (char**)malloc(2 * sizeof(char*));
            hashTable[hashSize].anagrams[0] = strs[i];  // 將當前字符串作為第一個異位詞
            hashTable[hashSize].size = 1;  // 異位詞組大小設置為 1
            hashTable[hashSize].capacity = 2;  // 初始容量設置為 2
            hashSize++;  // 增加異位詞組的總數量
        }
    }

    // 分配最終結果返回的內存
    char*** result = (char***)malloc(hashSize * sizeof(char**));  // 分配hash table大小的二維陣列
    *returnColumnSizes = (int*)malloc(hashSize * sizeof(int));  // 分配每組異位詞的大小
    *returnSize = hashSize;  // 返回異位詞組的總數量

    // 將hash table中的異位詞組和每組的大小放入結果中
    for (int i = 0; i < hashSize; i++) {
        result[i] = hashTable[i].anagrams;  // 異位詞列表
        (*returnColumnSizes)[i] = hashTable[i].size;  // 異位詞組的大小
    }

    free(hashTable);  // 釋放hash table的內存
    return result;  // 返回結果
}

Testing

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 定義一個結構來存儲異位詞組
typedef struct {
    int key[26];         // 26個字母的頻率作為鍵
    char** anagrams;     // 異位詞列表
    int size;            // 異位詞的數量
    int capacity;        // 異位詞列表的容量
} AnagramGroup;

// 比較兩個鍵是否相等（用於比較字母頻率陣列）
int keys_equal(int* key1, int* key2) {
    for (int i = 0; i < 26; i++) {
        if (key1[i] != key2[i]) {
            return 0;   // 如果兩個鍵的某個位置不相等，返回 0（表示不同）
        }
    }
    return 1;           // 所有位置相等，返回 1（表示相等）
}

// 計算字符串的字符頻率，並存儲在 key 陣列中
void calculate_key(char* str, int* key) {
    for (int i = 0; i < 26; i++) {
        key[i] = 0;     // 初始化 key 陣列，將所有字母的頻率設為 0
    }
    while (*str) {      // 遍歷字符串中的每個字符
        key[*str - 'a']++;  // 計算每個字符的頻率，並存儲到對應的 key 位置
        str++;          // 移動到下一個字符
    }
}

/**
 * 返回異位詞分組的動態數組，並且根據要求返回列大小和總組數。
 */
char*** groupAnagrams(char** strs, int strsSize, int* returnSize, int** returnColumnSizes) {
    // 初始容量為 100，之後會根據需要動態擴展
    int initialCapacity = 100;
    // 動態分配一個哈希表，用於存儲異位詞分組
    AnagramGroup* hashTable = (AnagramGroup*)malloc(initialCapacity * sizeof(AnagramGroup));
    int hashSize = 0;  // 異位詞組的數量
    
    // 初始化哈希表，將所有異位詞組的 size 和 capacity 設置為 0
    for (int i = 0; i < initialCapacity; i++) {
        hashTable[i].size = 0;
        hashTable[i].capacity = 0;
        hashTable[i].anagrams = NULL;  // 將異位詞列表初始化為空
    }

    for (int i = 0; i < strsSize; i++) {
        char* word = strs[i];  // 取得當前的字符串
        int key[26];           // 用來存儲當前字符串的字符頻率鍵
        calculate_key(word, key);  // 計算字符頻率鍵
        
        int found = 0;  // 用來標記是否在hash table中找到匹配的鍵

        // 嘗試在hash table中找到該鍵對應的異位詞組
        for (int j = 0; j < hashSize; j++) {
            if (keys_equal(hashTable[j].key, key)) {  // 如果鍵匹配
                found = 1;  // 找到匹配的異位詞組
                // 檢查當前異位詞組容量是否足夠
                if (hashTable[j].size == hashTable[j].capacity) {
                    hashTable[j].capacity = hashTable[j].capacity == 0 ? 2 : hashTable[j].capacity * 2;  // 動態擴展容量
                    hashTable[j].anagrams = (char**)realloc(hashTable[j].anagrams, hashTable[j].capacity * sizeof(char*));  // 重新分配內存
                }
                hashTable[j].anagrams[hashTable[j].size++] = strs[i];  // 將當前字符串加入異位詞組
                break;
            }
        }

        // 如果hash table中沒有找到匹配的鍵，則新增一個異位詞組
        if (!found) {
            // 檢查hash table的容量是否足夠，不夠就擴展容量
            if (hashSize == initialCapacity) {
                initialCapacity *= 2;  // hash table容量擴展為原來的兩倍
                hashTable = (AnagramGroup*)realloc(hashTable, initialCapacity * sizeof(AnagramGroup));  // 重新分配內存
            }
            // 將字符頻率鍵拷貝到新的異位詞組中
            memcpy(hashTable[hashSize].key, key, sizeof(int) * 26);
            // 初始化新的異位詞組，分配初始容量
            hashTable[hashSize].anagrams = (char**)malloc(2 * sizeof(char*));
            hashTable[hashSize].anagrams[0] = strs[i];  // 將當前字符串作為第一個異位詞
            hashTable[hashSize].size = 1;  // 異位詞組大小設置為 1
            hashTable[hashSize].capacity = 2;  // 初始容量設置為 2
            hashSize++;  // 增加異位詞組的總數量
        }
    }

    // 分配最終結果返回的memory
    char*** result = (char***)malloc(hashSize * sizeof(char**));  // 分配hash table大小的二維陣列
    *returnColumnSizes = (int*)malloc(hashSize * sizeof(int));  // 分配每組異位詞的大小
    *returnSize = hashSize;  // 返回異位詞組的總數量

    // 將hash table中的異位詞組和每組的大小放入結果中
    for (int i = 0; i < hashSize; i++) {
        result[i] = hashTable[i].anagrams;  // 異位詞列表
        (*returnColumnSizes)[i] = hashTable[i].size;  // 異位詞組的大小
    }

    free(hashTable);  // 釋放hash table的記憶體
    return result;  // 返回結果
}

int main() {
    char* strs[] = {"eat","tea","tan","ate","nat","bat"};
    int strsSize = 6;
    int returnSize;
    int* returnColumnSizes;
    char*** result = groupAnagrams(strs, strsSize, &returnSize, &returnColumnSizes);

    // 輸出結果
    for (int i = 0; i < returnSize; i++) {
        printf("[");
        for (int j = 0; j < returnColumnSizes[i]; j++) {
            printf("\"%s\"", result[i][j]);
            if (j < returnColumnSizes[i] - 1) {
                printf(", ");
            }
        }
        printf("]\n");
    }

    // 釋放記憶體
    for (int i = 0; i < returnSize; i++) {
        free(result[i]);
    }
    free(result);
    free(returnColumnSizes);
    return 0;
}

圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言
iThome鐵人賽
參賽組數
1064 組
團體組數
40 組
累計文章數
22201 篇
完賽人數
602 人
iT+看影片追技術 看影片追技術 看更多
熱門tag 看更多
15th鐵人賽 16th鐵人賽 13th鐵人賽 14th鐵人賽 12th鐵人賽 11th鐵人賽 鐵人賽 2019鐵人賽 javascript 2018鐵人賽 python 2017鐵人賽 windows php c# windows server linux css react vue.js
熱門問題
熱門回答
熱門文章
IT邦幫忙