n is the total number of words in the words array, and k is the average word length. For each word, we iterate through the words array and check if the concatenation results in a palindrome.

This approach causes a Time Limit Exceeded (TLE) error.

Method 2 - Smarter Brute Force

Perform a nested loop on the words array to evaluate pairs of words for palindrome pairs.
Note we dont have to concatenate the strings to check it, we can be smart about it. Rather than concatenating the strings to check for palindromes, the method isPalindrome checks the characters directly from both strings. This approach avoids the overhead of creating new strings.

On 17 Sept, 2022 - Gives TLE.

Code

[{"language":"Java","code":"public List<List<Integer>> palindromePairs(String[] words) {\n\tint n = words.length;\n\tList<List<Integer>> result = new ArrayList<>();\n\tfor (int i = 0; i < n; i++) {\n\t\tfor (int j = i + 1; j < n; j++) {\n\t\t\tif (isPalindrome(words[i], words[j])) {\n\t\t\t\tresult.add(Arrays.asList(i, j));\n\t\t\t}\n\t\t\tif (isPalindrome(words[j], words[i])) {\n\t\t\t\tresult.add(Arrays.asList(j, i));\n\t\t\t}\n\t\t}\n\t}\n\treturn result;\n}\n\nprivate boolean isPalindrome(String word1, String word2) {\n\tint start = 0;\n\tint l1 = word1.length();\n\tint l2 = word2.length();\n\tint end = l1 + l2 - 1;\n\n\twhile (start < end) {\n\t\tchar ch1 = start < l1 ? word1.charAt(start) : word2.charAt(start - l1);\n\t\tchar ch2 = end >= l1 ? word2.charAt(end - l1) : word1.charAt(end);\n\t\tif (ch1 != ch2) {\n\t\t\treturn false;\n\t\t}\n\t\tstart++;\n\t\tend--;\n\t}\n\treturn true;\n}","lang":"java","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> List</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">&#x3C;</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">List</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">&#x3C;</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">Integer</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">>></span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> palindrom

Related Tags