Sponsored
Sponsored
In this method, iterate through all possible pairs of words, concatenate them, and check if the concatenated result is a palindrome. Additionally, use the property that a string and its reverse can help identify palindrome pairs more efficiently.
Time Complexity: O(n^2 * k)
Space Complexity: O(n^2)
1/* C++ Solution for Brute Force Check with Reversed Strings */
2#include <iostream>
3#include <vector>
4#include <string>
5using namespace std;
6
7bool isPalindrome(const string& str) {
8 int left = 0, right = str.size() - 1;
9 while (left < right) {
10 if (str[left++] != str[right--]) return false;
11 }
12 return true;
13}
14
15vector<vector<int>> palindromePairs(vector<string>& words) {
16 vector<vector<int>> result;
17 int n = words.size();
18 for (int i = 0; i < n; ++i) {
19 for (int j = 0; j < n; ++j) {
20 if (i != j && isPalindrome(words[i] + words[j])) {
21 result.push_back({i, j});
22 }
23 }
24 }
25 return result;
26}The C++ implementation uses two nested loops to try all pairs and a helper function to check if the concatenated word forms a palindrome. It stores these pairs in a vector of vectors.
Instead of brute force, we can utilize a Trie data structure to store word reversals, which allows faster lookup for potential palindrome content between pairs. This method improves efficiency by focusing on checks only where relevant.
Time Complexity: O(n * k^2)
Space Complexity: O(n * k)
1/* Trie-based C Solution omitted due to complexity */This solution involves creating a Trie node structure to handle word entries with efficient searching capabilities.