LeetCode //C - 336. Palindrome Pairs - ToB企服应用市场:ToB评测及商务社交产业平台

typedef struct {
char* word;
int index;
} HashItem;
typedef struct {
HashItem* items;
int size;
} HashMap;
int hashFunc(char* str, int size) {
unsigned long hash = 5381;
int c;
while ((c = *str++)) {
hash = ((hash << 5) + hash) + c;
}
return hash % size;
}
HashMap* createHashMap(int size) {
HashMap* map = (HashMap*)malloc(sizeof(HashMap));
map->items = (HashItem*)calloc(size, sizeof(HashItem));
map->size = size;
return map;
}
void insertHashMap(HashMap* map, char* word, int index) {
int hash = hashFunc(word, map->size);
while (map->items[hash].word != NULL) {
hash = (hash + 1) % map->size;
}
map->items[hash].word = strdup(word); // Duplicate the word to avoid premature freeing
map->items[hash].index = index;
}
int searchHashMap(HashMap* map, char* word) {
int hash = hashFunc(word, map->size);
while (map->items[hash].word != NULL) {
if (strcmp(map->items[hash].word, word) == 0) {
return map->items[hash].index;
}
hash = (hash + 1) % map->size;
}
return -1;
}
bool isPalindrome(char* word, int left, int right) {
while (left < right) {
if (word[left++] != word[right--]) {
return false;
}
}
return true;
}
char* reverseString(char* word) {
int len = strlen(word);
char* reversed = (char*)malloc((len + 1) * sizeof(char));
for (int i = 0; i < len; i++) {
reversed[i] = word[len - i - 1];
}
reversed[len] = '\0';
return reversed;
}
int** palindromePairs(char** words, int wordsSize, int* returnSize, int** returnColumnSizes) {
*returnSize = 0;
int capacity = 10;
int** result = (int**)malloc(capacity * sizeof(int*));
*returnColumnSizes = (int*)malloc(capacity * sizeof(int));
// Hash map to store reversed words and their indices
int hashSize = 50000; // Increased size to reduce collisions
HashMap* hashMap = createHashMap(hashSize);
// Insert reversed words into the hash map
for (int i = 0; i < wordsSize; i++) {
char* reversed = reverseString(words[i]);
insertHashMap(hashMap, reversed, i);
free(reversed); // Free the reversed string after storing in the hash map
}
for (int i = 0; i < wordsSize; i++) {
int len = strlen(words[i]);
for (int j = 0; j <= len; j++) {
// Check if the suffix forms a palindrome and if the reverse of the prefix exists in the map
if (isPalindrome(words[i], j, len - 1)) {
char* prefix = strndup(words[i], j);
int index = searchHashMap(hashMap, prefix);
if (index != -1 && index != i) {
if (*returnSize == capacity) {
capacity *= 2;
result = (int**)realloc(result, capacity * sizeof(int*));
*returnColumnSizes = (int*)realloc(*returnColumnSizes, capacity * sizeof(int));
}
result[*returnSize] = (int*)malloc(2 * sizeof(int));
result[*returnSize][0] = i;
result[*returnSize][1] = index;
(*returnColumnSizes)[*returnSize] = 2;
(*returnSize)++;
}
free(prefix); // Safe to free the prefix here
}
// Check if the prefix forms a palindrome and if the reverse of the suffix exists in the map
if (j > 0 && isPalindrome(words[i], 0, j - 1)) {
char* suffix = strdup(words[i] + j);
int index = searchHashMap(hashMap, suffix);
if (index != -1 && index != i) {
if (*returnSize == capacity) {
capacity *= 2;
result = (int**)realloc(result, capacity * sizeof(int*));
*returnColumnSizes = (int*)realloc(*returnColumnSizes, capacity * sizeof(int));
}
result[*returnSize] = (int*)malloc(2 * sizeof(int));
result[*returnSize][0] = index;
result[*returnSize][1] = i;
(*returnColumnSizes)[*returnSize] = 2;
(*returnSize)++;
}
free(suffix); // Safe to free the suffix here
}
}
}
// Free the hash table and the words stored in it
for (int i = 0; i < hashSize; i++) {
if (hashMap->items[i].word != NULL) {
free(hashMap->items[i].word); // Free each stored word
}
}
free(hashMap->items);
free(hashMap);
return result;
}

复制代码