這是什麼

LeetCode 運用 Hash Function 的知識來解題。這邊提一下 Hash Function 的功能：

一串資訊（文字、數字等）經過 hash function 處理後會變成一串亂碼，該亂碼是無法 逆向 推導出處理前的內容。因為這個特質，經常用於保護密碼，例如登入系統的使用者密碼，資料庫儲存處理過的，如此一來，至少能防範有人竊取資料庫資料後，能夠登入系統。

Outcome first ===> Hash Function ===> 00c59c8ca032f5960cf417245ddff4fd8264ad7f92cbd13c9dbd671a021f999c

因為這個特性，進而有 Hash Table，將處理前後的資料儲存起來，供之後使用：

a => ca97...
b => 3e23...
c => 2e7d...
...
z => 594e...

有沒有覺得很眼熟？沒錯，套用在 JS 的概念，就是建立物件來儲存資訊：

const HashTable = {
  a: 'ca97...',
  b: '3e23...',
  c: '2e7d...',
  ...
  z: '594e...'
};

基於這點，LeetCode 內標註為 Hash Table 的題目，有很大的可能要製表儲存特定資訊，始得處理上能夠進行比對。

刷題：49. Group Anagrams

題目

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

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

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

Example 2:

Input: strs = [""]
Output: [[""]]

Example 3:

Input: strs = ["a"]
Output: [["a"]]

Constraints:

• 1 <= strs.length <= 104
• 0 <= strs[i].length <= 100
• strs[i] consists of lower-case English letters.

思考

拿到字後進行排序（按照 abcd 排序），接著 Hash Table 建立該字的 key，其 value 將放入一個陣列，儲存未排序的該字。
最後將 Hash Table 轉換成陣列即可。

解題

JS

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
const groupAnagrams = (strs) => {
  if (strs.length === 0) {
    return strs;
  }

  let hashTable = new Map();

  for (let i = 0; i < strs.length; i++) {
    const str = strs[i];
    let sortedStr = str.split('').sort().join('');

    if (hashTable.has(sortedStr)) {
      hashTable.get(sortedStr).push(str);
    } else {
      hashTable.set(sortedStr, [str]);
    }
  }

  return [...hashTable.values()];
};

Java

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs.length == 0) {
            return new ArrayList<>();
        }

        Map<String, List<String>> hashTable = new HashMap<>();

        for (String str : strs) {
            char[] ca = new char[26];

            for (char c : str.toCharArray()) {
                ca[c - 'a']++;
            }

            String keyStr = String.valueOf(ca);

            if (!hashTable.containsKey(keyStr)) {
                hashTable.put(keyStr, new ArrayList<>());
            }

            hashTable.get(keyStr).add(str);
        }

        return new ArrayList<>(hashTable.values());
    }
}

C

struct HashTable
{
    uint64_t **keys;
    char ***values;
    uint64_t *values_i_len;
    uint64_t size;
};

struct HashTable create_hash_table(uint64_t size)
{
    struct HashTable table;
    table.size = size;
    table.keys = calloc(size, sizeof(table.keys[0]));
    table.values = malloc(size * sizeof(table.values[0]));
    table.values_i_len = malloc(size * sizeof(table.values_i_len[0]));
    return table;
}

uint64_t convert_to_hash(const uint64_t *them)
{
    uint64_t hash = 7;

    for (uint64_t i = 0; i < 26; i++)
    {
        hash = hash * 31 + them[i];
    }

    return hash;
}

bool are_these_26_uint64_ts_equal(const uint64_t *this, const uint64_t *that)
{
    for (uint64_t i = 0; i < 26; i++)
    {
        if (this[i] != that[i])
        {
            return false;
        }
    }

    return true;
}

uint64_t *char_counts_mem_block;
uint64_t *next_char_int;

char **values_mem_block;
char **next_char;

void add_word_to_table(struct HashTable *table, char *word)
{
    uint64_t *char_counts = next_char_int;
    next_char_int += 26;

    for (char *walk = word; *walk; walk++)
    {
        char_counts[*walk - 'a']++;
    }

    uint64_t hash = convert_to_hash(char_counts);

    uint64_t entry_index = hash % table->size;
    uint64_t original_entry_index = entry_index;

    while (table->keys[entry_index] != NULL)
    {
        if (are_these_26_uint64_ts_equal(char_counts, table->keys[entry_index]))
        {
            break;
        }

        entry_index++;
        if (entry_index == table->size)
        {
            entry_index = 0;
        }
    }

    if (table->keys[entry_index] != NULL)
    {
        char **to_append_to = table->values[entry_index];

        to_append_to[table->values_i_len[entry_index]] = word;
        table->values_i_len[entry_index]++;
    }
    else
    {
        table->keys[entry_index] = char_counts;
        char **values_words = next_char;
        next_char += 64;
        values_words[0] = word;
        table->values[entry_index] = values_words;
        table->values_i_len[entry_index] = 1;
    }
}

char ***groupAnagrams(char **strs, int strsSize, int *returnSize, int **returnColumnSizes)
{
    char_counts_mem_block = calloc(26 * strsSize, sizeof(char_counts_mem_block[0]));
    next_char_int = char_counts_mem_block;

    values_mem_block = malloc(64 * strsSize * sizeof(values_mem_block[0]));
    next_char = values_mem_block;

    struct HashTable table = create_hash_table(strsSize);

    for (uint64_t i = 0; i < strsSize; i++)
    {
        char *word = strs[i];
        add_word_to_table(&table, word);
    }

    *returnSize = 0;
    for (uint64_t i = 0; i < table.size; i++)
    {
        if (table.keys[i] == NULL)
            continue;

        (*returnSize)++;
    }

    char ***results = malloc(*returnSize * sizeof(results[0]));
    *returnColumnSizes = malloc(*returnSize * sizeof(**returnColumnSizes));

    uint64_t result_index = 0;
    for (uint64_t i = 0; i < table.size; i++)
    {
        if (table.keys[i] == NULL)
            continue;

        results[result_index] = table.values[i];
        (*returnColumnSizes)[result_index] = table.values_i_len[i];

        result_index++;
    }

    return results;
}

看法

JS 與 Java 的寫法十分簡單，倒是 C，想起來 two sum 的時候，建立 Hash Table 是一件非常麻煩的事情，這邊也充分體現到這點，可怕。

結論

撇開 C 來說，這算是好解的題目，看懂要建立什麼樣的 Hash Table 即可解決。