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 */
2using System;
3using System.Collections.Generic;
4
5public class Solution {
6 public bool IsPalindrome(string str) {
7 int left = 0, right = str.Length - 1;
8 while (left < right) {
9 if (str[left++] != str[right--]) return false;
10 }
11 return true;
12 }
13
14 public IList<IList<int>> PalindromePairs(string[] words) {
15 IList<IList<int>> result = new List<IList<int>>();
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 result.Add(new List<int>{i, j});
20 }
21 }
22 }
23 return result;
24 }
25}The C# solution checks all word pairs using nested loops and employs a helper method `IsPalindrome` to determine if they form palindromes. The results are added to 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.