LeetCode //C - 336. Palindrome Pairs

336. Palindrome Pairs

You 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[j] (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: [[0,1],[1,0],[3,2],[2,4]]
Explanation: The palindromes are [“abcddcba”,“dcbaabcd”,“slls”,“llssssll”]
  Example 2:

   Input: words = [“bat”,“tab”,“cat”]
Output: [[0,1],[1,0]]
Explanation: The palindromes are [“battab”,“tabbat”]
  Example 3:

   Input: words = [“a”,“”]
Output: [[0,1],[1,0]]
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:

1. typedef struct {
2.     char* word;
3.     int index;
4. } HashItem;
6. typedef struct {
7.     HashItem* items;
8.     int size;
9. } HashMap;
11. int hashFunc(char* str, int size) {
12.     unsigned long hash = 5381;
13.     int c;
14.     while ((c = *str++)) {
15.         hash = ((hash << 5) + hash) + c;
16.     }
17.     return hash % size;
18. }
20. HashMap* createHashMap(int size) {
21.     HashMap* map = (HashMap*)malloc(sizeof(HashMap));
22.     map->items = (HashItem*)calloc(size, sizeof(HashItem));
23.     map->size = size;
24.     return map;
25. }
27. void insertHashMap(HashMap* map, char* word, int index) {
28.     int hash = hashFunc(word, map->size);
29.     while (map->items[hash].word != NULL) {
30.         hash = (hash + 1) % map->size;
31.     }
32.     map->items[hash].word = strdup(word);  // Duplicate the word to avoid premature freeing
33.     map->items[hash].index = index;
34. }
36. int searchHashMap(HashMap* map, char* word) {
37.     int hash = hashFunc(word, map->size);
38.     while (map->items[hash].word != NULL) {
39.         if (strcmp(map->items[hash].word, word) == 0) {
40.             return map->items[hash].index;
41.         }
42.         hash = (hash + 1) % map->size;
43.     }
44.     return -1;
45. }
47. bool isPalindrome(char* word, int left, int right) {
48.     while (left < right) {
49.         if (word[left++] != word[right--]) {
50.             return false;
51.         }
52.     }
53.     return true;
54. }
56. char* reverseString(char* word) {
57.     int len = strlen(word);
58.     char* reversed = (char*)malloc((len + 1) * sizeof(char));
59.     for (int i = 0; i < len; i++) {
60.         reversed[i] = word[len - i - 1];
61.     }
62.     reversed[len] = '\0';
63.     return reversed;
64. }
66. int** palindromePairs(char** words, int wordsSize, int* returnSize, int** returnColumnSizes) {
67.     *returnSize = 0;
68.     int capacity = 10;
69.     int** result = (int**)malloc(capacity * sizeof(int*));
70.     *returnColumnSizes = (int*)malloc(capacity * sizeof(int));
72.     // Hash map to store reversed words and their indices
73.     int hashSize = 50000;  // Increased size to reduce collisions
74.     HashMap* hashMap = createHashMap(hashSize);
76.     // Insert reversed words into the hash map
77.     for (int i = 0; i < wordsSize; i++) {
78.         char* reversed = reverseString(words[i]);
79.         insertHashMap(hashMap, reversed, i);
80.         free(reversed);  // Free the reversed string after storing in the hash map
81.     }
83.     for (int i = 0; i < wordsSize; i++) {
84.         int len = strlen(words[i]);
86.         for (int j = 0; j <= len; j++) {
87.             // Check if the suffix forms a palindrome and if the reverse of the prefix exists in the map
88.             if (isPalindrome(words[i], j, len - 1)) {
89.                 char* prefix = strndup(words[i], j);
90.                 int index = searchHashMap(hashMap, prefix);
91.                 if (index != -1 && index != i) {
92.                     if (*returnSize == capacity) {
93.                         capacity *= 2;
94.                         result = (int**)realloc(result, capacity * sizeof(int*));
95.                         *returnColumnSizes = (int*)realloc(*returnColumnSizes, capacity * sizeof(int));
96.                     }
97.                     result[*returnSize] = (int*)malloc(2 * sizeof(int));
98.                     result[*returnSize][0] = i;
99.                     result[*returnSize][1] = index;
100.                     (*returnColumnSizes)[*returnSize] = 2;
101.                     (*returnSize)++;
102.                 }
103.                 free(prefix);  // Safe to free the prefix here
104.             }
106.             // Check if the prefix forms a palindrome and if the reverse of the suffix exists in the map
107.             if (j > 0 && isPalindrome(words[i], 0, j - 1)) {
108.                 char* suffix = strdup(words[i] + j);
109.                 int index = searchHashMap(hashMap, suffix);
110.                 if (index != -1 && index != i) {
111.                     if (*returnSize == capacity) {
112.                         capacity *= 2;
113.                         result = (int**)realloc(result, capacity * sizeof(int*));
114.                         *returnColumnSizes = (int*)realloc(*returnColumnSizes, capacity * sizeof(int));
115.                     }
116.                     result[*returnSize] = (int*)malloc(2 * sizeof(int));
117.                     result[*returnSize][0] = index;
118.                     result[*returnSize][1] = i;
119.                     (*returnColumnSizes)[*returnSize] = 2;
120.                     (*returnSize)++;
121.                 }
122.                 free(suffix);  // Safe to free the suffix here
123.             }
124.         }
125.     }
127.     // Free the hash table and the words stored in it
128.     for (int i = 0; i < hashSize; i++) {
129.         if (hashMap->items[i].word != NULL) {
130.             free(hashMap->items[i].word);  // Free each stored word
131.         }
132.     }
133.     free(hashMap->items);
134.     free(hashMap);
136.     return result;
137. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。