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/* Java Solution for Brute Force Check with Reversed Strings */
2import java.util.ArrayList;
3import java.util.List;
4
5public class Solution {
6 public boolean isPalindrome(String str) {
7 int left = 0, right = str.length() - 1;
8 while (left < right) {
9 if (str.charAt(left++) != str.charAt(right--)) return false;
10 }
11 return true;
12 }
13
14 public List<List<Integer>> palindromePairs(String[] words) {
15 List<List<Integer>> result = new ArrayList<>();
16 for (int i = 0; i < words.length; ++i) {
17 for (int j = 0; j < words.length; ++j) {
18 if (i != j && isPalindrome(words[i] + words[j])) {
19 List<Integer> pair = new ArrayList<>();
20 pair.add(i);
21 pair.add(j);
22 result.add(pair);
23 }
24 }
25 }
26 return result;
27 }
28}The Java solution follows a similar approach with a helper method. It stores results in a List of Lists.
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 */
2This solution involves using a Trie to reverse words and manage lookup times, offering a more streamlined solution over brute force.