LeetCode //C - 336. Palindrome Pairs
336. Palindrome PairsYou are given a 0-indexed array of unique strings words.
A palindrome pair is a pair of integers (i, j) such that:
[*]0 <= i, j < words.length,
[*]i != j, and
[*]words + words (the concatenation of the two strings) is a palindrome
Return an array of all the palindrome pairs of words.
You must write an algorithm with O(sum of words.length) runtime complexity.
Example 1:
Input: words = [“abcd”,“dcba”,“lls”,“s”,“sssll”]
Output: [,,,]
Explanation: The palindromes are [“abcddcba”,“dcbaabcd”,“slls”,“llssssll”]
Example 2:
Input: words = [“bat”,“tab”,“cat”]
Output: [,]
Explanation: The palindromes are [“battab”,“tabbat”]
Example 3:
Input: words = [“a”,“”]
Output: [,]
Explanation: The palindromes are [“a”,“a”]
Constraints:
[*]1 <= words.length <= 5000
[*]0 <= words.length <= 300
[*]words consists of lowercase English letters.
From: LeetCode
Link: 336. Palindrome Pairs
Solution:
Ideas:
1. Reversing and Hashing:
[*]The main idea is to use a hash map (or hash table) to store the reversed versions of each word. This allows us to quickly check if there is a word in the array that, when concatenated with another word, forms a palindrome.
2. Palindrome Checks:
[*]For each word, the code checks if any prefix or suffix forms a palindrome. If a suffix is a palindrome, it checks if the reverse of the prefix exists in the hash map. If a prefix is a palindrome, it checks if the reverse of the suffix exists in the hash map.
[*]By checking both the prefix and suffix, the code can detect potential palindrome pairs that can be formed by concatenating two different words in different orders.
3. Efficient String Handling:
[*]The code carefully manages memory, ensuring that strings are duplicated when stored in the hash map. This avoids issues with accessing freed memory, which was a problem in earlier versions of the code.
4. Use of a Hash Map:
[*]The hash map is used to store the reversed words along with their indices. This allows for O(1) average-time complexity lookups, which is crucial for achieving the required efficiency given the constraints.
Code:
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.word != NULL) {
hash = (hash + 1) % map->size;
}
map->items.word = strdup(word);// Duplicate the word to avoid premature freeing
map->items.index = index;
}
int searchHashMap(HashMap* map, char* word) {
int hash = hashFunc(word, map->size);
while (map->items.word != NULL) {
if (strcmp(map->items.word, word) == 0) {
return map->items.index;
}
hash = (hash + 1) % map->size;
}
return -1;
}
bool isPalindrome(char* word, int left, int right) {
while (left < right) {
if (word != word) {
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 = word;
}
reversed = '\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);
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);
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, j, len - 1)) {
char* prefix = strndup(words, 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] = i;
result[*returnSize] = 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, 0, j - 1)) {
char* suffix = strdup(words + 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] = index;
result[*returnSize] = 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.word != NULL) {
free(hashMap->items.word);// Free each stored word
}
}
free(hashMap->items);
free(hashMap);
return result;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]